정렬

Oak_Cassia·2021년 12월 18일
0

Data Structure

목록 보기
3/5

Sort

실행 방법

  1. 비교 정렬(comparative sort): 비교할 각 키 값을 한 번에 두 개씩 비교하여 교환함으로써 정렬을 실행하는 방식
  2. 분배식 정렬(distribute sort): 키 값을 기준으로 하여 자료를 여러 개의 부분집합으로 분해하고 각 부분집합을 정렬함으로써 전체를 정렬하는 방식

정렬 장소

  1. 내부 정렬(internal sort): 컴퓨터 메모리 내부에서 정렬
    1). 비교식
    교환방식: 키를 비교하고 교환하여 정렬하는 방식(선택 정렬, 버블 정렬, 퀵 정렬)
    삽입방식: 키를 비교하고 삽입하여 정렬하는 방식(삽입 정렬, 셸 정렬)
    병합방식: 키를 비교하고 병합하여 정렬하는 방식(2-way 병합, n-way 병합)
    선택방식: 이진 트리를 사용하여 정렬하는 방식(힙 정렬, 트리 정렬)

  2. 외부 정렬(external sort): 메모리의 외부인 보조 기억 장치에서 정렬
    파일을 부분 파일로 분리하여 각각을 내부 정렬 방법으로 정렬하여 병합하는 방식(2-way 병합, n-way 병합)


selection sort

전체 원소 중에서 기준 위치에 맞는 원소를 선택해 자리를 교환하는 방식
공간 복잡도 n, 시간 복잡도 O(n2)O(n^2), 어떤 경우에서나 비교 횟수가 같다.

bubble sort

인접한 원소 두개를 비교하여 자리를 교환하는 방식
공간 복잡도 n, 시간 복잡도 O(n2)O(n^2)
최악의 경우: 역순으로 정렬된 경우
최선의 경우: 순서대로 정렬된 경우

quick sort

전체 원소에 대해 정렬을 수행하지 않고 기준 값을 중심으로 왼쪽 부분집합과 오른쪽 부분 집합으로 분할한다. 왼쪽 부분집합에는 기준값보다 작은 원소를 이동시키고 오른쪽 부분집합에는 기준 값 보다 큰 원소들을 이동시킨다. 이 때 기준 값을 ‘pivot’ 이라 한다.
피벗은 가운데 위치한 원소 또는 첫째 원소, 마지막 원소로 정할 수 있고 별도의 수식을 사용하여 정하기도 한다.
분할과 정복을 반복 수행하여 퀵정렬을 완성한다.
분할: 정렬할 자료들을 기준값을 중심으로 두 개로 나눠 부분집합을 만든다.
정복: 부분집합 안에서 기준값의 정렬 위치를 정한다.

  1. 왼쪽 끝에서 오른쪽으로 이동하며 크기를 비교한다. 피벗보다 크거나 같은 원소를 찾아 L로 표시한다. L은 R과 만나면 더 이상 오른쪽으로 이동하지 못하고 멈춘다.
  2. 오른쪽 끝에서 왼쪽으로 이동하며 크기를 비교한다. 피벗보다 작은 원소를 찾아 R로 표시한다. R은 L을 만나면 멈춘다.
  3. A. 1과 2에서 찾은 L과 R이 있는 경우 설 교환하고 L과 R의 현재위치에서 1과 2를 진행한다.
    B. L과 R이 같은 원소에서 만난 경우 피벗과 R의 원소를 서로 교환한다. 교환된 자리를 피벗 위치로 확정하고 현재 단계의 퀵 정렬을 끝낸다.
  4. 피벗의 확정된 위치를 기준으로 만들어진 새로운 왼쪽 부분집합과 오른쪽 부분집합에 대해서 1~3의 퀵 정렬을 순환적으로 반복 수행한다. 모든 부분 집합의 크기가 1이하가 되면 퀵 정렬 종료

하나의 배열 안에서 교환이 진행되므로 공간 복잡도: n
평균 시간 복잡도 OO(nlognn\log n)
최선의 경우에 피벗에 의해 왼쪽 부분집합과 오른쪽 부분집합이 반반 나뉘는 경우이다. OO(nlognn\log n)
최악의 경우는 피벗이 극단적으로 한쪽에 치우쳐져 있을 경우 O(n2)O(n^2)

insertion sort

정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방식
sorted subset과 unsorted subset로 나뉘어 있다고 가정한다.
공간 복잡도 n
최선의 경우 O(n) 정렬된 경우
최악의 경우: O(n2)O(n^2) 역순으로 정렬된 경우, 평균O(n2)O(n^2)

shell sort

일정한 간격(interval)으로 떨어져 있는 자료들 끼리 부분집합을 구성하고, 각 부분집합에 있는 원소에 대해 삽입정렬을 수행하는 작업을 반복하여 전체원소를 정렬하는 방법
간격을 점점 줄여 1이 되면 삽입 정렬을 수행한다.
임베디드 시스템에 주로 사용. 간격에 따른 그룹별 정렬 방식이 하드웨어로 구현하기 적합하다.

공간 복잡도 O(n)
시간복잡도 O(n1.5)O(n^{1.5}) , Hibbard의 간격 2k12^k-1
, O(n1.25)O(n^{1.25}) 실험적인 결과 간격을 얼마로 설정하나에 따라 달린다.
최악 O(n2)O(n^2)
최선 O(n)O(n)

merge sort

여러 개의 정렬된 자료집합을 병합하여 하나의 정렬된 집합으로 만드는 정렬 방법
분할: 자료를 두개의 부분 집합으로 분할한다.
정복: 부분집합에 잇는 원소를 정렬한다.
결합: 정렬된 부분집합들을 하나의 집합으로 정렬하여 결합한다.

분할 단계: 전체자료 집합을 한 개의 원소를 가진 부분집합이 될 때 까지 분할한다.
정복, 결합: 부분집합 두 개를 정렬하여 하나로 결합한다. 하나의 집합이 될 때 까지 반복한다.
공간복잡도 2n
시간 복잡도 O(nlogn)O(n\log n)

radix sort

정렬할 원소의 키값에 해당하는 버킷에 원소를 분배했다가 버킷의 순서대로 원소를 꺼내는 방법을 반복한다. 키 값의 자릿수 만큼 기수 정렬을 반복한다. 10진수는’0~9’ 10개의 버킷 사용
숫자를 부분적으로 비교하는 정렬 방법.
제한적인 범위 내에 있는 숫자에 대해서 각 자릿수 별로 정렬하는 알고리즘. 비교 정렬 알고리즘 보다 빠르다.

  1. 키값의 1의 자리에 대해서 기수 정렬을 수행한다. 정렬한 원소의 키값의 1의 자리에 맞춰 버킷에 분배한다. 버킷에 분배되어 있는 원소들을 버킷 0부터 버킷9 까지 순서대로 꺼내고, 꺼낸 순서대로 저장한다.
  2. 키 값의 10의 자리에 대해서 기수 정렬을 수행한다.
    공간: 원소 수 n, 버킷 큐에 대한 추가 공간
    시간: 원소 수 n, 키 값의 자리수 d, 버킷 수를 결정하는 기수 r O(d(n+r))

heap sort

힙을 이용해 정렬된 값을 얻는 방법
루트와 마지막 원소의 자리를 바꾸고 힙의 크기를 줄인다.
힙의 크기가 1이 되면 정렬을 멈춘다.
공간: n 개의 메모리, 힙을 저장할 공간, 시간 O(nlogn)O(n\log n)

tree sort

이진 탐색 트리를 이용한 방법. (중위 순회: 오름차순)
공간: n + 이진탐색 트리를 저장할 공간
시간 O(nlogn)O(n\log n)

profile
rust로 뭐할까

0개의 댓글