정렬 알고리즘 정리(1)

자료를 정렬하는데 사용하는 자료의 값을 키라고 한다. Key

파일크기에 따라 정렬이 되면 파일크기가 키다.

정렬의 효율성은 정렬 대상이 되는 자료가 비교연산과 자료 이동연산의 횟수에 의해 결정된다.

(퀵 정렬은 O(nlogn)이다 ) 아래는 시간복잡도에 따른 성능 우선순위다.

알고리즘에 따라 비교 연산이 많이 수행되는 경우와 자료 이동의 연산이 많이 수행되는 경우로 나눌 수 있다. 

정렬을 수행해야 하는 자료의 크기가 크다면 같은 횟수의 연산이라 하더라도 비교연산이 많은 알고리즘이 이동 연산이 많은 알고리즘보다 성능이 우수

(자료크기가 큼, 비교연산 > 이동연산 이렇게 되는 알고리즘이 더 낫다, 왜냐면 자료의 크기가 클 경우 이동해야하는 데이터의 크기가 증가하기 때문)

그리고 저장된 자료의 상태에 따라 평균 효율성과 최악인 경우의 효율성은 차이가 있다.

정렬의 안정성이란.. 같은 키 값을 가지는 자료들을 입력 순서 그대로  정렬하는지를 가리킨다?

몇가지를 찾아봤다 

버블 정렬은 두 값을 비교할 때 왼쪽이 더 큰 경우만 교환하므로 같은 크기의 레코드는 원래의 순서를 유지하는 특성이 있다. 위 예에서 두 개의 i가 있는데 정렬된 후에도 두 i의 순서가 바뀌지 않는다는 것을 알 수 있는데 이런 특성을 안정성이라고 한다

* 안정 정렬

• 거품 정렬 (Bubble sort)
  - 한글 : http://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC
  - 영문 : http://en.wikipedia.org/wiki/Bubble_sort
  
• 삽입 정렬 (Insertion sort)
  - 한글 : http://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC
  - 영문 : http://en.wikipedia.org/wiki/Insertion_sort
  
• 교환 정렬 (Comb sort)
  - 영문 : http://en.wikipedia.org/wiki/Comb_sort
  
• 합병 정렬 (Merge sort)
  - 한글 : http://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC
  - 영문 : http://en.wikipedia.org/wiki/Merge_sort
  
• 계수 정렬 (Counting sort)
  - 영문 :  http://en.wikipedia.org/wiki/Counting_sort
  
• 버킷 정렬 (Bucket sort)
  - 영문 :  http://en.wikipedia.org/wiki/Bucket_sort
  
• 기수 정렬 (Radix sort)
  - 한글 :  http://ko.wikipedia.org/wiki/%EA%B8%B0%EC%88%98_%EC%A0%95%EB%A0%AC
  - 영문 :  http://en.wikipedia.org/wiki/Radix_sort
  

* 불안정 정렬

• 선택 정렬 (Selection sort)
  - 한글 : http://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC
  - 영문 : http://en.wikipedia.org/wiki/Selection_sort
  
• 쉘 정렬 (Shell sort)
  - 한글 : http://ko.wikipedia.org/wiki/%EC%85%B8_%EC%A0%95%EB%A0%AC
  - 영문 : http://en.wikipedia.org/wiki/Shell_sort

• 힙 정렬 (Heap sort)
  - 한글 : http://ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC
  - 영문 : http://en.wikipedia.org/wiki/Heapsort
  
• 퀵 정렬 (Quick sort)
  - 한글 : http://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC
  - 영문 : http://en.wikipedia.org/wiki/Quicksort 

그 중복된 값의

순서가 바뀌지 않으면 안정 정렬(stable sort)

순서가 바뀌면 불안정 정렬(unstable sort)로 구분 합니다.

좀더 이해를 돕자면, 아래 표에 중복값 3 이 빨강, 파랑 순으로 정렬되어 있는데,

정렬 후에도  빨강, 파랑 순으로 정렬되어 있느냐? 아니냐? 입니다.

빨강, 파랑의 순서가 바뀌지 않으면, 안정 정렬

빨강, 파랑의 순서가 바뀌면, 불안정 정렬

이렇게 구분 되는것입니다.

2, 5, 1, 3, 4, 3	1, 2, 3, 3, 4, 5	1, 2, 3, 3, 4, 5
초기값	안정 정렬 (순서 변화X)	불안정 정렬 (순서 변화O)

아..같은 키 값을 가지는 자료들을 입력 순서 그대로 정렬하는지를 가리킨다..(그러니까 입력순서 그대로를 보장하느냐 마느냐를 따지는듯..)

그런데 보통은 정렬에 사용되는 키가 2개 이상인 경우에 의미가 있다고 한다. 다중키 정렬에서 차이를 발생시키는데..

안정정렬이라면 기존 정렬내용이 유지되기 때문에 단순히 우선순위가 낮은 키 부터 높은 순으로 여러번 정렬만 한다면 자동으로 다중 키 정렬이 가능

반면 불안정 정렬은 기존의 정렬 내용이 유지되지 않기 때문에 다중 키 정렬의 키 값 비교를 위한 별도의 비교 로직이 추가되어야 한다.

예를들어 파일 크기와 파일 이름2가지 키가 있다면 먼저 파일 크기로 정렬하고 다음 파일 이름으로 정렬할때 불안정의 경우(안정은 그냥 순서대로 하면됨) 먼저 정렬한 내용이(파일 크기 순) 보존되지 않기 때문에 안정정렬처럼 순서대로 한다고해서 되지 않음...그런데

효율성이 높은 정렬 알고리즘은 보통  불안정 정렬인 경우가 많다.!

교환 : 선택, 버블, 퀵 // 말그대로 키 값을 비교하고 자료를 교환하는 방식

삽입 : 삽입, 쉘    // 키 값을 비교하고 자료를 삽입하는 방식

병합 : 병합 (2-way n-way)    //키 값을 비교하고 자료를 병합

분배 : 기수 정렬    //키 값을 여러개의 부분 집합으로 분배 후 이를 이용하여 자료를 정렬하는 방식

선택 : 히프    // 트리 자료구조 등 특정 자료구조를 통하여 정렬하는 방식