소팅

https://swexpertacademy.com/main/help/review/contentsReviewDetail.do?contentId=9091

Sorting

sorting의 구분

inplace outplace

stable unstable

online offline

소팅의 구현

배열과 List의 차이

배열을 이용한 구현

장점 : 배열의 주소가 연속적으로 잡혀있어서 접근이 빠르다. 데이터 참조가 쉽다.

단점: 크기가 고정되어 있어 사이즈 증감이 어렵다. 중간값 변경시 이후의 데이터를 모두 변경해야함.

LinkedList를 이용한 구현

장점 : 배열의 단점을 극복,크기가 유동적이고, 중간 값 변경이 용이함. 단점 : 매번 새로운 메모리를 할당하여 연결하기 때문에 성능이 느림. 포인터 공간이 추가로 생성때문에 공간적으로 비효율적임.

sorting 종류

시간 복잡도와 방법

• BubbleSort
  • 가장 기본적인 소팅 방법
  • 현재 배열 요소와 다음 배열 요소를 비교한 다음, 조건에 걸리면 교환한다.
  • 맨 앞 원소가 방울 처럼 올라가는 것 처럼 보여서 bubble sort
  • 8 9 1 3 2
    8 1 9 3 2
    8 1 3 9 2
    8 1 3 2 9
    1 8 3 2 9
    1 3 8 2 9
    1 3 2 8 9
    1 2 3 8 9
• Selection Sort
  • 인덱스를 먼저 정하고(선택하고) , 해당 index에 들어갈 원소를 찾는다.
  • index를 낮은 곳부터 증가시키면서 찾아서 넣는다.
  • 가장 작은것 또는 가장 큰것을 찾아서 교환한다.
  • 1 8 9 3 2 (1 다 낮네)
    1 2 9 3 8
    1 2 3 9 8
    1 2 3 8 9
• Insertion Sort
  • 맨 앞 원소부터,자기 앞의 원소들과 비교하여 자리를 찾아 삽입하는 방식
  • 현재 원소보다 큰 원소들은 한 칸씩 뒤로 미루고
  • 자신보다 작은 원소가 나왔을 때 그 뒤에 삽입하는 방식
  • 9 8 1 3 2 (key = 9) index 0
    9 8 1 3 2 (key = 8) 1
    8 9 1 3 2 (key = 8) 2
    8 1 9 3 2 (key = 1) 3
    1 8 9 3 2
    1 8 3 9 2 (key = 3) 4
    1 3 8 9 2
    1 3 8 2 9 (key =2) 5
    1 3 2 8 9
  • 정렬이 되어 있는 경우 빠르게 동작함.
  • 이에 간간히 사용됨.

핵심 정렬

• Merge Sort (D&C 를 이용한 방식)
  • 구현시 여분의 배열이 필요함. 메모리 여유가 있을 때 사용하는 것이 좋음.

• QuickSort
  • pivot을 기준으로 작은 건 왼쪽, 큰건 오른쪽으로 나누어 pivot의 위치를 찾고
  • 각각 왼쪽과 오른쪽을 반복함.
  • 여분의 배열이 필요하지 않음.
  • 이미 정렬된 배열의 경우 pivot을 제외한 배열을 재정렬하여 O(N^2)의 최악의 경우.
  • 이러한 최악을 피하기 위해 pivot을 설정시 랜덤으로 하는 방법이 존재함.
• HeapSort
  • 완전 이진트리, 우선순위 큐를 위해 만들어진 자료구조를 사용.
  • heap 이 뭐죠? (참조)
  • 여분의 배열이 필요하다.
• Tim Sort
• radixSort

표로 정리

Java에서는?

Comparable에 대한 내용은 다음을 참조.(link)

JAVA sort comparable 참조

 

추후 보강(2022.02.07 작성)

보강 내용

코드, 표 삽입, 공부 조금 더 해서 내용 채우기