[Algorithm] 정렬 ①

- 정렬

Bubble sort, Insertion sort, Selection sort => 상대적으로 단순하고 느림.

Quick sort, Merge sort, Heap sort => 상대적으로 빠름.

Radix sort 

 

- Selection Sort

1. 데이터 중에서 가장 큰 값을 찾고 마지막 자리의 값과 위치를 바꿈. => 가장 큰 값이 마지막 위치를 갖게 됨.

2. 가장 큰 값을 제외하고 남아 있는 데이터 중에서 가장 큰 값을 찾고 마지막 자리의 값과 위치를 바꿈.

   이때, 정렬하고자 하는 데이터 중에 가장 큰 값이 마지막 자리에 있는 경우 그 위치에 그대로 둠.

3. 2번을 반복함. 2개의 데이터가 남을 때까지 반복한 후 그 둘 중 큰 값을 뒷자리로 보냄. 정렬은 완료됨.

 

Ex) 배열 A[1...n]을 정렬하는 코드

 selectionSort ( A [ ] , n ) {

      for last <- n downto 2 {

           A [ 1 . . . last ] 중 가장 큰 수 A [ k ]를 찾는다 ;

           A [ k ] <-> A [ last ] ; } } => A [ k ]와 A [ last ]의 값을 교환

=> for 루프는 n-1번 반복

     A [ 1 . . . last ] 중 가장 큰 수를 찾기 위한 비교 횟수 : n-1 , n-2 , . . . , 2 , 1

     교환은 상수시간 작업

=> 시간복잡도 : T(n) = (n-1) + (n-2) + . . . + 2 + 1 = O(n^2) => 최악, 최선, 평균의 경우 고려하지 않아도 됨.

 

- Buble Sort

1. 맨 앞의 데이터가 바로 옆 값과 비교해서 크다면 서로의 자리를 바꿈.

2. 바뀐 자리에서도 바로 옆 값과 비교해서 크다면 서로의 자리를 바꿈.

3. 바뀐 자리에서 바로 옆 값과 비교해 작다면 그 자리에 둠.

4. 바로 옆 값을 가지고 1 , 2 , 3번을 반복. 

5. 모든 데이터를 거쳤다면 다시 맨 앞의 데이터를 가지고 1 , 2 , 3 , 4번을 반복.

 

 

Ex) 배열 A[1...n]을 정렬하는 코드

 bubbleSort ( A [ ] , n ) {

      for last <- n downto 2 {

           for i <- 1 to last-1

           if ( A [ i ] > A [ i + 1 ] ) then A [ i ] <-> A [ i + 1 ] ; } } => 교환 

=> for 루프는 n-1번 반복

     for 루프는 각각  n-1 , n-2 , . . . , 2 , 1번 반복

     교환은 상수시간 작업

=> 시간복잡도 : T(n) = (n-1) + (n-2) + . . . + 2 + 1 = O(n^2) 

 

- Insertion Sort : 삽입정렬

1. 데이터를 삽입함.

2. 데이터가 삽입된 위치의 앞자리의 데이터가 더 크다면 그 값을 뒤로 이동시킴.

3. 계속해서 비교하여 원래의 값들은 뒤로 이동시키고 삽입한 데이터를 앞으로 이동시킴.

 

Ex) 배열 A[1...n]을 정렬하는 코드

 insertionSort ( A [ ] , n ) {

      for i <- 2 to n {

           A [ 1 ... i ]의 적당한 자리에 A [ i ]를 삽입한다. } }

=> for 루프는 n-1번 반복

     A [ i ]의 삽입은 최악의 경우 i - 1번 비교

=> 최악의 경우 : T(n) = (n-1) + (n-2) + . . . + 2 + 1 = O(n^2) => 단, 1번의 비교로 정렬을 마칠 수도 있음.