10/24/2016

기본정렬 (Sorting Algorithm)

1. (Sorting Algorithm) 정렬 알고리즘 기본내용 

일반적으로 정렬은 가지고 있는 Data 를 Ascending 오름차 순으로 or
Descending 내림차순으로 가지고 있는 data list를 순서를 변경하는 것이다.

이를 한정적으로 숫자에 그리고, 적용범위를 위와 같이 한정짓으면 위와 같이 되겠지만,
적용범위를 넓히면 다양하게 Sorting을  할 수도 있겠다.

일단 목적이 기본적으로 Sorting Algorithm 학습이기에 알아둬야 할 기본 용어 부터 알아보자.

  • ascending sort or ascending order    (오름차순 정렬 ):  1,2,3,4
  • descending sort or descending order (내림차순 정렬):  4,3,2,1


2. 정렬 (Sorting Algorithm ) 비교 및 pseudo code

일반적으로 많이 사용되는 정렬 알고리즘이며 pseudo code 이들을 간단히 살펴보자.



이외에도 다른 많은 Sorting Algorithm 이 존재하며 이를 다 알기가 힘들어서 여기서 다루지는 않겠다.


  • 상위 정렬들의 Working Time 비교분석 

  https://www.toptal.com/developers/sorting-algorithms/


 3. 정렬 알고리즘 기본학습

기본적인 Sort만 다루겠지만, Heap sort는 priority Queue 함께 다루겠다.


3.1 기본적으올 알아둬야 할 정렬 알고리즘 
  • Bubble Sort  
  • Insertion Sort  
  https://en.wikipedia.org/wiki/Insertion_sort
  https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC

버블정렬은 알 것이지만, Insertion Sort는 한번 살펴보자.

  https://www.tutorialspoint.com/data_structures_algorithms/bubble_sort_algorithm.htm
  https://www.tutorialspoint.com/data_structures_algorithms/insertion_sort_algorithm.htm


3.2 대표적으로 좋은 성능 내주는 정렬 알고리즘  

  • Quick Sort 
  • Merge Sort 
위 두 정렬은 divide and conquer algorithm 이며, sorting 하는 방법도 유사하다.
divide하는 방식은 같지만, conquer의 역할이 다를 뿐이다.

Quick는 divide 다 한 후, 교환하는 방식으로 간다고 정렬하지만,
Merge는 divide 다 한 후, 별도의 Memory 공간에 이 정렬되는 과정을 넣어 이것을 정렬한다.

이 둘의 차이는 Memory의 사용량의 차이

  https://www.tutorialspoint.com/data_structures_algorithms/quick_sort_algorithm.htm
  https://www.tutorialspoint.com/data_structures_algorithms/merge_sort_algorithm.htm

A. Quick Sort
  1. data array 중 한 data를 선택하여 이를 Pivot하고 기준으로 정한다.
  2. Partitioning은 이는 array를 다시 순서를 맞추는 작업이다. 
  3. Partitioning에서 얻은 큰 값을 기준으로 sub-array 작업을 반복적으로 한다.

Partitioning
      왼쪽에서   pivot 위치까지   pivot 보다 작은 데이타 위치를 찾는다.
      오른쪽에서 pivot 위치까지  pivot 보다 큰    데이타 위치를 찾는다.


  https://en.wikipedia.org/wiki/Quicksort
  https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC
  http://www.cquestions.com/2008/01/c-program-for-quick-sort.html

  아래의 소스는 Quick sort C로 구현을 해본것이다.


B. Merge sort

  https://en.wikipedia.org/wiki/Merge_sort
  https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC


  • Merge sort examples 

  https://www.tutorialspoint.com/data_structures_algorithms/merge_sort_program_in_c.htm
  http://yujuwon.tistory.com/entry/%EB%B3%91%ED%95%A9%EC%A0%95%EB%A0%ACMerge-Sort

  http://nukestorm.tistory.com/54

Tags:

댓글 없음 :

댓글 쓰기

피드 구독하기: 댓글 ( Atom )