선택 정렬(Selection sort)
현재 위치에 들어갈 값을 찾아 정렬하는 배열. 현재 위치에 저장 될 값의 크기가 작냐, 크냐에 따라 최소 선택 정렬와 최대 선택 정렬로 구분 할 수 있다.
- 정렬 되지 않은 인덱스의 맨 앞에서 부터, 이를 포함한 그 이후의 배열값 중 가장 작은 값을 찾아간다.(정렬되지 않은 인덱스의 맨 앞은, 배열의 시작위치)
- 가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꿔준다.
- 다음 인덱스에서 위 과정을 반복.
배열이 어떻게 되어있던지간에 전체 비교를 진행하므로 시간복잡도는 O(n^2)이다.
공간복잡도는 단 하나의 배열에서만 진행하므로 O(n)이다.
삽입 정렬(Insertion sort)
삽입 정렬은 현재 위치에서, 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아, 그 위치에 삽입하는 배열 알고리즘이다.
- 두 번째 자료부터 시자하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬한다.
- 즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째 자료와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다.
- 처음 키값은 두 번째 자료부터 시작한다.
삽입 정렬의 시간복잡도는 O(n^2)이다.
공간복잡도는 단 하나의 배열에서만 진행하므로 O(n)이다.
버블 정렬(Bubble sort)
버블 정렬은 매번 연속된 두개 인덱스를 비교하여, 정한 기준의 값을 뒤로 넘겨 정렬하는 방법.
- 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.
- 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다.
선택 정렬과 같이 배열이 어떻게 되어있던지간에 전체 비교를 진행하므로 시간복잡도는 O(n^2)이다.
공간복잡도는 단 하나의 배열에서만 진행하므로 O(n)이다.
합병 정렬(Merge sort)
분할 정복 방식으로으로 설계된 알고리즘이다. 분할 정복은 큰 문제를 반으로 쪼개 문제를 해결해 나가는 방식. 분할은 배열의 크기가 1보다 작거나 같을 때 까지 반복한다.
- 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
- 합병 정렬은 다음의 단계들로 이루어진다.
(1) 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
(2) 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
(3) 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다. - 합병 정렬의 과정
추가적인 리스트가 필요하다.
각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다.
합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계 이다.
시간 복잡도는 O(NlogN)이다.
퀵 정렬(Quick sort)
퀵 정렬은 합병 정렬처럼 분할 정복(Divide and conquer)을 이용하여 정렬을 수행하는 알고리즘.
pivot point라고 기준이 되는 값을 하나 설정하는데, 이 값을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮기는 방식으로 정렬을 진행한다. 이를 반복하여 분할된 배열의 크기가 1이되면 배열이 모두 정렬 된 것이다.
- 분할(Divide) : 입력 배열을 피벗을 기준으로 비 균등하게 2개의 부분 배열(왼쪽 : 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
- 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
- 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
시간 복잡도는 O(NlogN)이다.
