정렬

• 안정정렬
  • 정렬 후에도 같은 데이터에 대해서는 초기 순서가 유지되는 정렬
  • 3,2(1),2(2),1 이 있을때 오름차순으로 정렬하면 1,2(1),2(2),3 으로 2의 순서가 유지되는 정렬
  • 삽입정렬, 병합정렬, 버블정렬
• 불안정 정렬
  • 정렬 후에도 같은 데이터에 대해서는 초기 순서가 유지되지 않는 정렬
  • 퀵정렬, 선택정렬, 계수정렬
• 제자리 정렬(In memory sort)
  • 주어진 공간외에 별도의 공간이 필요로 하지 않는 정렬

 

• Comparisons Sorting
  • 선택 정렬(Selection Sort)
    • 데이터를 넣을 위치를 선택 후 해당 위치에 넣을 데이터를 찾아 정렬하는 방식
    • 오름차순 정렬
      • i번째 위치 선택
      • i~n번 위치에서 가장 작은 값 찾기 
      • i번째 위치와 값 변경
      • i += 1
      • 총 n번 수행
    • 시간 복잡도
      • 최소, 최악, 평균  : O(n^2)
    • 제자리 정렬, 불안정 정렬
  • 삽입 정렬(Insertion Sort)
    • 2번째 원소부터 해당 원소가 들어갈 자리를 찾을 때까지 원소를 하나씩 당기는 정렬
    • 오름차순 정렬
      • 2번째 원소부터 시작
      • 시작 위치의 값을 temp에 저장
      • 시작 위치 이전의 값과 비교하여 temp보다 크다면 해당 위치 원소 오른쪽으로 한칸 이동
      • 작거나 같다면 해당 위치 오른쪽에 temp값 저장 
      • 시작 위치 1 증가하여 반복
    • 시간 복잡도
      • 최소 : 정렬되어 있을 경우 O(n)
      • 최악, 평균 : O(n^2)
    • 제자리 정렬, 안정 정렬
  • 버블 정렬(Bubble Sort)
    • 인접한 두 원소를 비교하여 교환하는 정렬
    • 1회전 마다 마지막 원소의 값이 결정 됨
    • 오름차순 정렬 
      • i가 i+1보다 크다면 i와 i+1 원소 변경
      • i가 최대 길이-1 될때까지 반복
      • i가 최대 길이-1까지 도달 했을 때 최대 길이 - 1
      • 전체 원소의 개수만큼 반복
    • 시간 복잡도
      • 최소, 최악, 평균 : O(n^2)
    • 제자리 정렬, 안정 정렬
  • 병합 정렬(Merge Sort)
    • 분할 정복을 통한 방식
    • 오름차순 정렬
      • 배열의 반반 나누어 왼쪽, 오른쪽으로 각각 진행
      • 배열의 원소가 하나가 될때까지 분할 진행
      • 두개의 나눠진 배열의 첫번째 원소부터 비교해서 작은 값을 원본배열에 저장
      • 빼온 배열의 인덱스 증가
      • 둘중 한곳의 숫자를 모두 뺄때까지 진행
      • 아직 숫자가 남은 배열의 값을 원본배열에 모두 저장
      • 각각의 나뉜 배열은 정렬된 상태가 됨
    • 안정정렬
    • 제자리 정렬이 아님
      • 나눈 배열을 임시 저장할 공간이 필요
    • 시간 복잡도
      • 최소, 최악, 평균 : O(nlogn)
  • 퀵 정렬(Quick Sort)
    • 분할 정복을 통한 정렬 방식
    • 오름차순 정렬
      • 배열의 원소중 하나를 선정(피벗)
      • 피벗을 왼쪽은 피벗보다 작은값, 오른쪽은 피벗보다 큰값이 오도록 재배치 : 분할
      • 피벗을 기준으로 두 배열을 나눔
      • 나눈 배열에 대해 위의 과정 다시 수행
      • 최소 하나의 원소가 남을때 까지 수행
    • 매번 피벗을 최소 또는 최대값이 지정되어 매번 모든 배열을 검사하므로 O(n^2) 시간 복잡도가 걸림
    • 피벗을 랜덤으로 고르던가, 3개중 중간값으로 하던가 해서 최악의 경우를 피할 수는 있지만 그래도 최악의 경우 O(n^2)
    • 시간 복잡도
      • 최악 : O(n^2)
      • 최소, 평균 : O(nlogn)
    • 제자리 정렬, 불안정 정렬
  • 병합 정렬과 퀵 정렬 비교
    • 퀵 정렬 : 피벗을 기준으로 나누면서 정렬함
    • 병합 정렬 : 일단 끝까지 나눈 후 합치면서 정렬함
    • 퀵정렬이 더 빠른 이유
      • 메모리의 지역성 특성 때문에 퀵정렬이 더 빠르다
      • 데이터는 더 빠르게 접근하기 위해 캐시에 저장하여 사용 한다.
      • 근데 병합 정렬의 경우 제자리 정렬이 아니어서 다른 공간이 또 필요로 한다.
      • 때문에 캐시 미스가 날 확률이 더 크고 미스가 날 경우 다시 메모리에서 갔다 오기 때문에 시간이 더 걸린다.
      • 반면 퀵 정렬은 제자리 정렬로 처음 데이터 가지고 정렬을 수행하기 때문에 캐시 힛 확률이 더 크고 결국 더 빨리 데이터를 가져와 정렬을 수행하게 된다.
  • 힙 정렬(Heap Sort)
    • 힙 자료구조를 활용한 정렬
    • 루트 노드이 값은 항상 최소, 최대값을 갖는 다는 성질을 이용
    • 오름차순 정렬
      • 최소 힙 구성
      • 루트와 마지막 노드의 값을 바꾼 후 힙 사이즈를 하나 줄임(루트 값 추출)
      • 힙의 사이즈가 1보다 크면 위의 과정 반복
    • 시간 복잡도
      • Build Heap : O(n)
      • N번의 heapify : O(nlogn)
      • O(n)+O(nlogn) = O(nlogn)
    • 제자리 정렬, 불안정 정렬
• Non-Comparisons Sorting
  • 계수 정렬(Counting Sort)
    • 비교 연산이 이루 
    • 이름 처럼 개수를 세서 정렬하는 방식
    • 원본 데이터의 최대값만큼 tmp 배열 생성
    • tmp에 원본 데이터 배열의 데이터의 개수를 세서 저장
    • tmp배열에 누적합을 계산
    • 원본 데이터의 뒤에서 부터 누적합으로 정렬 수행
    • 시간복잡도
      • O(n+k) : k - 배열의 최대값
    • 배열의 크기보다 최대값이 작다면 효율적
    • k가 크게 되면 k만큼 배열의 크기도 커지므로 메모리 낭비가 심함
      • 배열에 200,1,100000000000 이있다면 굉장히 낭비가 시함
  •  기수 정렬(Radix Sort)
    • 각 자리수별로 버킷이라는 공간에 넣어 정렬을 수행
    • 모든 데이터의 길이가 같아야한다는 단점이 있어 활용 범위가 제한적
    • 숫자, 문자 모두 정렬 가능
    • LSD : 가장 덜 중요한 자리부터 정렬, 숫자라면 1의 자리부터 정렬
      
      • 중간과정에 정렬이 되지 않아 정렬이 다 수행되야 볼 수 있음
    • MSD: 가장 중요한 자리부터 정렬, 숫자라면 가장 큰 자리부터 정렬
      • 정렬 중간에 정렬이 될 수 있지만 별도의 과정과 메모리 사용 필요
    • LSD 예시
      • 1의 자리를 기준으로 해당 자리의 버킷에 해당 원소 넣음
      • 모든 원소에 대해 수행 후 버킷의 첫번째 부터 넣은 순서대로 다시 원본배열에 저장
      • 그 다음 자릿수에 대해서 다시 수행
    • 시간복잡도
      • O(dn)) : d - 정렬할 데이터의 자릿수