정렬 알고리즘

정렬 알고리즘 : 자료를 좀 더 의미있는 구조로 만드는 알고리즘

1. 정렬의 개요

-   컴퓨터 기억 장소 내에 저장 되어 있는 자료를 키에 따라 원하는 순서로 재배치하는 작업을 정렬(Sort)이라고 합니다.

-  자료를 작은 순부터 큰 순으로 정렬하는 방법을 오름 차순이라고 하고, 큰 순부터 작은 순으로 정렬하는 방법을 내림 차순이라고 합니다.

-   정렬 알고리즘의 선택에는 

   컴퓨터 시스템의 특성 고려, 
   자료의 양 분석. 
   자료의 초기 정렬 상태 고려, 
   키 값의 분포 상황 고려, 
   키 비교 횟수 계산, 
   필요한 작업 공간 

   고려로 분류할 수 있습니다.

2.  합병 정렬

-   작은 크기의 리스트들을 각각 정렬한 후, 이들을 합병하고, 

   크기가 2배인 리스트를 과정을 되풀이하여 전체 리스트를 정렬하는 방법을 합병 정렬(Merge Sort)이라고 합니다.

3. 퀵 정렬

-  주어진 리스트에서 피봇(pivot) 원소를 선택하여 피봇 원소를 기준으로 분할한 후, 분할된 부분 리스트를 정렬시키는 과정을 재귀적으로 적용함으로써 전체 리스트를 정렬하는 방법을 퀵 정렬(Quick Sort)이라고 합니다.

-  퀵 정렬 알고리즘과 병합 정렬 알고리즘의 평균적인 시간 복잡도는 Ο(nlog2n)입니다.
  그러나 실제적으로 퀵 정렬이 병한 정렬보다 빠르게 정렬을 수행합니다. 

여기에 재미있게 웹페이지 상에서 다양한 정렬 알고리즘을 보여주는 페이지를 소개 합니다.

Sorting Algorithm Animations

http://www.sorting-algorithms.com/

These pages show 8 different sorting algorithms on 4 different initial conditions. These visualizations are intended to:

• Show how each algorithm operates.
• Show that there is no best sorting algorithm.
• Show the advantages and disadvantages of each algorithm.
• Show that worse-case asymptotic behavior is not always the deciding factor in choosing an algorithm.
• Show that the initial condition (input order and key distribution) affects performance as much as the algorithm choice.

The ideal sorting algorithm would have the following properties:

• Stable: Equal keys aren't reordered.
• Operates in place, requiring O(1) extra space.
• Worst-case O(n·lg(n)) key comparisons.
• Worst-case O(n) swaps.
• Adaptive: Speeds up to O(n) when data is nearly sorted or when there are few unique keys.

There is no algorithm that has all of these properties, and so the choice of sorting algorithm depends on the application.

Sorting is a vast topic; this site explores the topic of in-memory generic algorithms for arrays. External sorting, radix sorting, string sorting, and linked list sorting—all wonderful and interesting topics—are deliberately omitted to limit the scope of discussion.