정렬 (2)

* 퀵 정렬(Quick Sort)

분할 정복(Divide and Conquer)방식으로 속도가 빠른 알고리즘

교환 정렬의 일종으로 속도가 매우 빠르다.

기준 값(피벗)보다 큰 것을 오른쪽에 작은 것을 왼쪽으로 나누고 분할시켜

분할된 자료의 개수가 1일 때 까지 반복한다.

 

 

  

---

 

* 바이너리 서치(Binary Search)

퀵 정렬과 마찬가지로 분할 정복(Divide and Conquer)방식으로 속도가 빠른 알고리즘

임의로 중간값을 지정해주고 찾는값과 크고 작음을 비교해가며 찾는 방식

배열에 저장된 데이터는 정렬되어 있어야 한다.

 

 

찾고자 하는 값 = 4 일 경우

 

1

2

3

4

5

6

7

8

9

Low = 1

High = 9

Middle = 5            3 < 5 

 

1

2

3

4

5

6

7

8

9

Low = 1

High = 5

Middle = 3            4 > 3

 

1

2

3

4

5

6

7

8

9

Low = 3

High = 5

Middle = 4            4 = 4

 

1

2

3

4

5

6

7

8

9

end

 

#include <iostream>
#include <stdlib.h>
#include <time.h>
#define size 30
using namespace std;

int Binary_Search(int num,int* a);
void Quick_Sort(int* a,int low, int high);
int Part(int* a,int low, int high);

int main()
{
 int a[size];
 int temp,num;

 srand((unsigned int)time(NULL));

 for(int i=0; i<size; i++)
 {
  temp = rand()%100 + 1;
  a[i] = temp; 
  for(int j=0; j<i; j++)
  {
   if(a[i] == a[j])
   {
    i--;
    break;
   }
  }  
 }
 cout<<"Before quick sort "<<endl;
 cout<<"----------------------------------------------------------"<<endl;
 for(int i=0; i<size; i++)
 {
  cout.width(3);
  cout<<a[i]<<" "; 
  if((i+1)%15 == 0)
   cout<<endl;
 }

 Quick_Sort(a,0,size-1); 
 
 cout<<endl<<endl;
 cout<<"After Quick Sort "<<endl;
 cout<<"----------------------------------------------------------"<<endl;
 for(int i=0; i<size; i++)
 {
  cout.width(3);
  cout<<a[i]<<" "; 
  if((i+1)%15 == 0)
   cout<<endl;
 }

 cout<<endl<<endl<<"input : ";
 cin>>num;
 if(Binary_Search(num,a) == 0)
  cout<<"There is not number"<<endl;
 else
  cout<<"index : " <<Binary_Search(num,a)<<endl; 

 return 0;
}

int Binary_Search(int num, int* a)
{
 int middle = 0;
 int index = -1;
 int start = 0;
 int end = size-1;

 while(start <= end)
 {
  middle = (start + end) / 2;  
  if(num == a[middle])  
  {
   index = middle;
   break;
  }
  else if(num < a[middle]) 
   end = middle - 1;
  
  else if(num > a[middle]) 
   start = middle + 1;
 }
 return index+1;
}

void Quick_Sort(int* a,int low, int high)
{
 int pivot;
 if(high>low)
 { 
  Part(a,low,high);  
  pivot=Part(a,low,high);

  Quick_Sort(a,low,pivot-1);  //피벗 왼쪽부분 재귀함수 호출
  Quick_Sort(a,pivot+1,high);  //피벗 오른쪽부분 재귀함수 호출
 }
}

int Part(int* a,int low, int high)
{
 int temp;
 int pivot=low;
 low++;

 while(low <= high)
 {
 
  while(a[low]<a[pivot])       
   low++;
  
  while(a[high]>a[pivot])         
   high--;   

  if(low<high)        
  {   
   temp=a[low];
   a[low]=a[high];
   a[high]=temp;
  }
 }
 temp=a[high];    
 a[high]=a[pivot];
 a[pivot]=temp;

 return high;   
}