정렬(sorting)

bubble sort

---

 

#include<stdio.h>
void sort(int *v, int n){

 int i,j;
 int tmp;
 int flag;

 

 for(i = 0 ; i< n-1  ; i++){
  flag = 0; 
  for(j = 0  ; j<n-1-i ; j++){
    if(v[j] > v[j+1]){

      tmp = v[j];
      v[j] = v[j+1];
      v[j+1] = tmp;

      flag = 1;

   }

  }
  if(flag == 0) break;  // sorting이 끝나면 for문 나오게 함
 }
}
void main()
{
 int x[10] = {75,27, 49,10,93,23,76,11,53,77};
 int j;

 for(j =0 ; j< 10 ; j++ ){
  printf(" %d",x[j]);
 }

 puts("\n");
 sort(x,10);
 for(j = 0 ; j<10 ; j++)
  printf(" %d",x[j]);
 puts("\n");

}

선형탐색

---

 

#include<stdio.h>

void sort(int *v, int n){

 int i,j;
 int tmp;
 int flag;

 

 for(i = 0 ; i< n-1 ; i++){
  flag = 0; 
  for(j = 0  ; j<n-1-i ; j++){
   if(v[j] > v[j+1]){

    tmp = v[j];
    v[j] = v[j+1];
    v[j+1] = tmp;

    flag = 1;

   }

  }
  if(flag == 0)break;     
 }
}

int search(int v[], int n, int what){

 //선형 탐색 > 처음부터 끝까지 찾아봄
 int i;
 for(i = 0; i < n ; i++){
  if(what == v[i]) return i;
  
 }
 return -1;
}
void main()
{
 int x[10] = {75,27, 49,10,93,23,76,11,53,77};
 int j;
 int found;

 

 found = search(x,10,23);     // 찾고자 하는 데이터 값( 23 )의 인덱스 리턴( x[5] )
 printf("%d\n", found);     // 못찾으면 -1 리턴

 for(j =0; j< 10 ; j++ ){
  printf(" %d",x[j]);
 }

 puts("\n");
 sort(x,10);

 for(j = 0 ; j<10 ; j++)
  printf(" %d",x[j]);
 puts("\n");

 

}

이진 탐색 : sorting이 된 상태에서 데이터 검색

---

 

 

#include<stdio.h>

void sort(int *v, int n){

 int i,j;
 int tmp;
 int flag;

 

 for(i = 0 ; i< n-1 ; i++){
  flag = 0;
  for(j = 0  ; j<n-1-i ; j++){
   if(v[j] > v[j+1]){

    tmp = v[j];
    v[j] = v[j+1];
    v[j+1] = tmp;

    flag = 1;
   }

 

  }
  if(flag == 0)break; 

 }
}

int search(int v[], int n, int what){

 

 int low, high, mid;

 low = 0;
 high = n-1;

 while(low <= high){
  mid = (low +high)/2;
  if(what < v[mid]){
   high = mid-1;

  }else if(what >v[mid]){
   low =mid+1;

  }else {     // what이 v[mid] 같은 경우! 데이터 찾음
   return v[mid];
  }
 }
 return -1;

}
void main()
{
 int x[10] = {75,27, 49,10,93,23,76,11,53,77};
 int j;
 int found;

 sort(x,10);

 found = search(x,10,23);     // 찾고자 하는 데이터 값(23)의 인덱스 리턴(x[5])
 printf("%d\n", found);     // 못찾으면 -1 리턴

}