정렬 알고리즘

 

 | 정렬

 

 데이터를 특정한 조건에 따라 일정한 순서가 되도록 다시 배열하는 일

 

 

 

| 1. 선택 정렬(Selection Sort)

 

 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

 

 1) 주어진 리스트 중에 최솟값을 찾는다.

 2) 그 값을 맨 앞에 위치한 값과 교체한다.

 3) 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

 

 

 선택 정렬 알고리즘은 n-1개, n-2개, ...., 1개씩 비교를 반복하고,

 이에 따른 시간복잡도는 O(n^2)이고 공간복잡도는 O(n)이다.

 

 

               

            [선택 정렬 애니메이션]

 

 

 

 > C에서의 선택 정렬 구현

 

  

 

 > JAVA에서의 선택 정렬 구현

 

  

 

 

 

 

| 2. 삽입 정렬(Insertion Sort)

 

 현재 위치에서, 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아, 그 위치에 삽입하는 배열 알고리즘으로 다음과 같은 순서로 이루어 진다.

 

 1) 삽입 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스는 별도의 변수에 저장해주고, 비교 인덱스를 현재 인덱스 -1로 잡는다.

 2) 별도로 저장해 둔 삽입을 위한 변수와, 비교 인덱스의 배열 값을 비교한다.

 3) 삽입 변수의 값이 더 작으면 현재 인덱스로 비교 인덱스의 값을 저장해주고, 비교 인덱스를 -1하여 비교를 반복한다.

 4) 만약 삽입 변수가 더 크면, 비교 인덱스 +1에 삽입 변수를 저장한다.

 

 

> 성능 분석

 - 최선의 경우 : O(n), 입력받은 배열이 이미 정렬이 되어 있는 경우 

  (리스트가 추가될 때마다 바로 앞의 리스트하고만 비교)

 - 최악의 경우 : O(n^2), 입력받은 배열이 정렬하고자 하는 방법의 역순일 경우

  (리스트가 추가될 때마다 앞의 모든 리스트와 비교)

 - 평균의 경우 : O(n^2)

 - 공간복잡도 : O(n), 다른 공간을 필요로 하지 않음

 

 

 > C에서의 삽입 정렬 구현

 

  

 

 > JAVA에서의 삽입 정렬 구현

 

  

 

 

 

 

| 3. 버블 정렬(Bubble Sort)

 

 정렬 알고리즘 중 활용도가 높고, 구현도 쉬워 많은 프로그래머들이 즐겨쓰는 알고리즘으로, 자신과 인접한 데이터와 비교하여 정렬하는 방식이다

 

 > 기본 로직

  1) 첫 번째 인덱스 부터 시작한다. 현재 인덱스 값과, 다음의 인덱스 값을 비교한다.

  2) 만약 현재 인덱스가 더 크면, 다음 인덱스와 바꿔준다.

  3) 다음 인덱스가 더 크면, 교환하지 않고, 다음 두 연속된 배열 값을 비교한다.

  4) 이를 (배열의 크기 - 현재까지 순환한 횟수) 만큼 반복한다.

 

 

 > 성능 분석

  - 최선의 경우 : O(n^2), 비교횟수는 n(n-1)/2번이고, 자리교환은 발생하지 않음. 자료가 이미 정렬되어 있는 경우

  - 최악의 경우 : O(n^2), 비교횟수는 최선의 경우과 같고, 자리교환 횟수는 n(n-1)/2번이다. 자료가 역순으로 정렬되어 있는 경우

  - 평균 시간 복잡도는 O(n^2)

  - 공간복잡도는 O(n)

 

 

 > C에서의 버블 정렬 구현

 

  

 

 > JAVA에서의 버블 정렬 구현

 

  

 

 

 

 

| 4. 합병 정렬(Merge Sort)

 

 합병 정렬은 큰 문제를 반으로 쪼개 문제를 해결하는 방식인 분할 정복(Divide and Conquer) 방식으로 설계된 알고리즘이다.

 

 > 기본 로직

  1) 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는

  2) 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.

  3) 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.

  4) 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

 

  * http://palpit.tistory.com/128 자세함

 

 > 성능 분석

  - 시간 복잡도 : 일반적으로 O(NlogN)

  - 공간 복잡도 : O(2n), 정렬을 위한 배열을 하나 더 생성하기 때문이다.

 

 

 

 

| 5. 퀵 정렬(Quick Sort)

 

 퀵 정렬은 정렬할 전체 원소에 대해 정렬을 수행하지 않는다.

 기준 값(피벗)을 중심으로 전체 원소들을 왼쪽 부분집합과 오른쪽 부분집합으로 분할하고,

 왼쪽 부분집합에는 기준 값보다 작은 원소들을, 오른쪽 부분집합에는 기준 값보다 큰 원소들을 위치시킨다.

 

 * http://palpit.tistory.com/126 

 

 > 성능 분석

  - 최악의 경우 : O(n^2)

  - 최선/평균의 경우 : O(nlogn)

 

 

 

 

 

[참조]

위키피디아

http://djflexible.github.io/blog/algorithm-insertionSort.html 

http://hsp1116.tistory.com/33 

http://www.jynote.net/490