기수 정렬(Radix Sort)
기수 정렬이라 함은?? 정렬할 Item이 숫자인 경우에만 가능한 정렬 방식으로, 숫자의 자리 수를 이용하여 크기 비교하는 정렬.그림과 함께 보자. 1. 위의 그림과 같이 [32, 87, 20, 92, 57] 로 나열되어 있는 배열을 기수 정렬을 하려고 한다.우선 일의 자리수에 대해서만 비교하도록 한다. 각 배열 값의 일의 자리 수에 해당되는 값을 큐에 집어 넣는다.32 같은 경우엔 일의 자리가 2이므로 2 index를 가진 큐에 집어넣고 나머지도 같은 방식으로 큐에 집어넣은다.큐에 다 집어 넣으면, 0 index 부터 차례대로 다시 가져온다.가져온 결과 값이 [20, 92, 32, 57, 87] 이며, 이 값은 일의 자리에 대한 sorting 결과 이다. 2. 십의 자리 수에 대해 다시 기수 정렬을 한다..
2013. 7. 6.
쉘 정렬(Shell Sort)
삽입 정렬의 단점을 보완한 정렬 방식. 삽입 정렬의 단점??? 삽입 정렬은 한칸씩 이동하면서 비교하기 때문에 만일 가장 멀리 떨어진 곳에서 비교가 이루어진다면 이동 시 많은 오버헤드가 발생할 수 있다. 그 단점을 보완하기 위해 만들어진 방식!! 그림과 함께 살펴보도록 하자 1. 주어진 배열에 대해 반으로 쪼갠 후, 쪼갠 블록을 각 쌍으로 삽입 정렬을 시행한다. 예를 들면 {3,2}, {8,1}, {0,4} 가 쌍으로 삽입 정렬이 실행되고 결과는 {2,3}, {1,8}, {0,4} 로 나타날 것이다. 2. 삽입 정렬이 완료된 블록에 대해 다시 반으로 쪼갠 후, 쪼갠 블록의 각 index를 다시 삽입 정렬로 정렬한다. {2,1,3,8}, {0,4} => {1,2,3,8}, {0,4} 3. 결과에 대해 다시 ..
2013. 6. 24.