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로 구현을 해본것이다.

/*
Quick sort example 3
*/
#include <stdio.h>
//SETTING QUICK SORT, PIVOT POSITION
#define PIVOT_LEFT
//#define PIVOT_RIGHT
#define PIVOT_LEFT_SWAP
//#define PIVOT_RIGHT_SWAP
#define SORT_ORDERING_ASCEND // , DESCENDING 4,3,2,1
int partition(int data[], int left, int right)
{
#if defined(PIVOT_LEFT)
int pivot = data[left];
int start = left+1;
int end = right;
#elif defined(PIVOT_RIGHT)
int pivot = data[right];
int start = left;
int end = right-1;
#endif
int tmp;
while(start <= end) //first to right-1
{
#if defined(SORT_ORDERING_ASCEND) // ASCENDING ,1,2,3,4
while(data[start] <= pivot && start <= end) start++;
while(data[end] > pivot && start <= end) end--;
#else // DESCENDING 4,3,2,1
while(data[start] > pivot && start < end) start++;
while(data[end] <= pivot && start <= end) end--;
#endif
if(start < end ){
tmp = data[start];
data[start] = data[end];
data[end] = tmp;
}else
break;
}
#if defined(PIVOT_LEFT_SWAP) // last swap
tmp = data[left];
data[left] = data[end];
data[end] = tmp;
return end;
#elif defined(PIVOT_RIGHT_SWAP)
tmp = data[start];
data[start] = data[right];
data[right] = tmp;
return start;
#endif
}
/*
int partition2(int arr[], int left, int right)
{
int first=left;
int pivot=arr[first];
int tmp;
left++; // next.
while(left <= right)
{
//ASCENDING ,1,2,3,4
while(arr[left] <= pivot && left < right) left++;
while(arr[right] > pivot && left <= right) right--;
//DESCENDING 4,3,2,1
// while(arr[left] > pivot && left < right) left++;
// while(arr[right] <= pivot && left <= right) right--;
if(left < right){ // can't find value
tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
}else
break;
}
tmp = arr[first];
arr[first] = arr[right];
arr[right] = tmp;
return right; //index;
}
*/
int quicksort(int data[], int left, int right)
{
int index=0;
if (left < right)
{
index = partition(data,left,right);
quicksort(data,left,index-1);
quicksort(data,index+1,right);
}
}
void sort_print(int arr[], int Lens)
{
int i=0;
for (i = 0; i < Lens; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Second Quick sort
void quickSort2(int arr[], int left, int right) {
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
/* partition */
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};
/* recursion */
if (left < j)
quickSort2(arr, left, j);
if (i < right)
quickSort2(arr, i, right);
}
int main(void) {
// your code goes here
int arr1[] = {5, 2, 1, 8, 3, 6, 4, 7 , 9 , 12, 11, 10 };
int arr2[] = {5, 2, 1, 8, 3, 6, 4, 7 , 9 , 12, 11, 10 };
int Lens1 = sizeof(arr1) / sizeof(int);
int Lens2 = sizeof(arr2) / sizeof(int);
printf("Quick Lenght=%d\n",Lens1);
printf("------1st TEST \n");
sort_print(arr1, Lens1);
quicksort(arr1, 0, Lens1 - 1);
sort_print(arr1, Lens1);
printf("------2nd TEST \n");
sort_print(arr2, Lens2);
quickSort2(arr2, 0, Lens2 - 1);
sort_print(arr2, Lens2);
return 0;
}
view raw langc_algo_quicksort.c hosted with ❤ by GitHub

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 )