배열 정렬 포인트
화이트보드에 배열의 수도코드를 그릴 수 있게 되기
단순 비효율 3개 : 버블, 선택, 삽입 정렬. 인접 값끼리 스왑하는 정렬들로 최악의 경우 시간복잡도가 너무 높기 때문에 범위가 작은 문제이거나 특정 조건을 만족할 때만 효율성이 있다.
삽입 정렬을 그나마 많이 쓴다.
효율 3개 : 퀵, 힙, 병합 정렬. 시작점 끝점을 잡고 중간을 재귀적으로 계속 쪼개서 맞추는 정렬로 어느정도 균일한 러닝타임을 보장하기 때문에 자주 쓰인다.
버블 정렬(Bubblesort)
https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html
서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.
선택 정렬과 기본 개념이 유사하다.
장점
구현이 매우 간단하다.
단점
순서에 맞지 않은 요소를 인접한 요소와 교환한다.
하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.
일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않는다.
선택 정렬(selection sort)
https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html
제자리 정렬(in-place sorting) 알고리즘의 하나
입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법
해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 넣는다.
두 번째 순서에는 두 번째 위치에 남은 값 중에서의 최솟값을 넣는다.
과정 설명
주어진 배열 중에서 최솟값을 찾는다.
그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다.
선택 정렬(selection sort) 알고리즘의 특징
장점
자료 이동 횟수가 미리 결정된다.
단점
안정성을 만족하지 않는다.
즉, 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.
삽입 정렬(insertion sort)
https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html
손안의 카드를 정렬하는 방법과 유사하다.
새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입한다.
새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬된다.
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.
장점
안정한 정렬 방법
레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다.
대부분위 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.
단점
비교적 많은 레코드들의 이동을 포함한다.
레코드 수가 많고 레코드 크기가 클 경우에 적합하지 않다.
퀵 정렬(quick sort)
https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html
‘찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)’가 개발한 정렬 알고리즘
퀵 정렬은 불안정 정렬 에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 에 속한다.
분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법
병합 정렬(merge sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할한다.
분할 정복(divide and conquer) 방법
문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.
합병 정렬(merge sort)
https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html
‘존 폰 노이만(John von Neumann)’이 제안한 방법
일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬 에 속하며, 분할 정복 알고리즘의 하나 이다.
분할 정복(divide and conquer) 방법
문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.
과정 설명
리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
단점
만약 레코드를 배열(Array)로 구성하면, 임시 배열이 필요하다.
제자리 정렬(in-place sorting)이 아니다.
레크드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.
장점
안정적인 정렬 방법
데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다. (O(nlog₂n)로 동일)
만약 레코드를 연결 리스트(Linked List)로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
제자리 정렬(in-place sorting)로 구현할 수 있다.
따라서 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 졍렬 방법보다 효율적이다.
힙 정렬(heap sort)
https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html
최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법
내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.
과정 설명
정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 만든다.
내림차순을 기준으로 정렬
그 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다.
삭제되는 요소들(최댓값부터 삭제)은 값이 감소되는 순서로 정렬되게 된다.
장점
시간 복잡도가 좋은편
힙 정렬이 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 크거나 작은 값 몇개만 필요할 때
