정렬
오늘은 알고리즘에서 매우 중요한 정렬에 대해서 말해보겠습니다. 이 글은 위키백과와 구글을 이용하여 작성했습니다.
정렬 알고리즘 뜻 : 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다.
정렬 알고리즘은 무수히 많다. 오늘은 정렬 알고리즘들중에서 4개의 정렬 알고리즘들을 소개할 것이다.
1. 선택정렬(Selection Sort)
선택정렬이란 ?
나열한 것중에 가장 작은 또는 가장 큰 것을 선택하여 앞 또는 끝으로 보내는 작업을 반복하면 최종적으로 크기 순서대로 정렬이 되는 방식이다.
순서 :
- 주어진 리스트 중에 최소값을 찾는다.
- 그 값을 맨 앞에 위치한 값과 교체한다
- 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다
오른쪽 그림과 같이 가장 작은 수를 선택한다음 교환하면서 정렬을 하는 형태이다.
옆 그림을 보면 첫번째 교환한 후, 1의 색깔이 바뀐다. 저것은 첫번째 레코드 위치에 1을 놓아서 다음 정렬을 할 때 저것은 이용하지 않는 것이다. 이말은 정렬 할 때 첫번째때는 6개의 숫자를 정렬하는데 1이라는 숫자가 맨 앞에 장착을 했으므로 5개의 숫자를 정렬한다. 이렇게 정렬할 숫자가 0개가 될 때까지 정렬을 한다.
C에서 사용되는 선택 정렬 소스 코드
2. 삽입정렬(InsertionSort)
삽입 정렬이란?
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.
오른쪽은 삽입정렬을 간단하게 표현한 것이다.
1. 1과 5를 비교한다. 1은 5보다 작으니까 5의 앞으로 간다. 1은 더이상 비교할 숫자가 없으므로 가만히 있는다.
2. 5와 2를 비교한다. 2가 더 작으니까 5의 앞으로 간다. 2는 1과 비교를 한다. 그런데 2가 더 크므로 2는 1의 앞에 있는다.
3. 3은 5와 비교를 한다. 3은 5보다 작으므로 5의 앞으로 이동한다. 3은 2와 비교한다. 그런데 2보다 크므로 가만히 있는다.
4. -2와 는 1보다도 작으므로 5부터 1까지 비교한다음 맨앞으로 이동한다.
5. 6은 5와 비교한다. 그런데 6이 5보다 크므로 가만히 있는다.
C에서 사용되는 삽입 정렬 소스 코드
3. 버블 정렬(Bubble Sort)
버블 정렬이란?
인접한 두 수를 비교하여 큰 수를 뒤로 보내는 간단한 정렬 알고리즘이다.
오른쪽은 버블 정렬을 간단하게 그림으로 표현한 것이다. 이건 살짝 선택정렬이랑 삽입정렬을 섞어 놓았다고 생각하면 된다. 왜냐하면 이것은 선택 정렬이랑은 그 앞에게 정해지면 그 앞의 숫자를 빼고 n-1개의 형태로 1개씩 좁혀 가면서 정렬하는 것이다. 이건 단지 가장 큰것을 정해서 그 숫자를 빼고 비교하는 것이다. 그리고 버블정렬이 삽입 정렬이랑 비슷한 이유는 서로 숫자를 비교하면서 교환하기 때문이다.
버블 정렬 소스 코드
