c 정렬 select & insert & bubble sort

Selection Sort 선택정렬

• 이미 정렬된 값을 제외한 값들을 탐색하면서 그 중에서 가장 작은 값들을 찾고, 작은 순서대로 자리에 맞게 SWAP하기

• 오름차순으로 정렬하기

  # include <stdio.h>
  # define SWAP(x,y,t) (t=x, x=y, y=t)
    
  void selectSort(int list[], int num){
      int i, j, min,temp;
      for (i=0; i<n-1; i++){  // i : 리스트의 처음부터 마지막-1 인덱스까지
          min = i;
          for (j=i+1; j<n; j++) // j : i 다음부터 리스트 끝까지 훑으면서
              if (list[j] < list[min]) // 최솟값 찾기
                  min = j;
         	SWAP(list[i], list[min], temp);
          // i 인덱스 값과 제일 작은 값의 자리를 바꿔주기!
      }
  }
  

  • 내림차순 정렬을 하고 싶다면 최댓값 찾도록 if (list[j] < list[min]) 대소 표시를 > 로 바꾸기

  • SWAP() : temp는 x, y 두 개의 값을 바꿀때 임시로 값을 저장하려고 만든 변수

    • x = 1 y = 3 –> x = y 해버리면 x = 3 y = 3 –> (???) 이렇게 되니까
    • temp에 x 값을 대피(?)시켜놓고 x=y, y=temp 하기

• EX) int list[] = {5,2,1,8,3}

  int main(){
      int list[] = {5,2,1,8,3};
      selectSort(list, 5);
  }
  

  • i = 0 일 때,
    • min = 0
    • j = 1 , 2, 3, 4 를 탐색하며 최솟값찾기 ( j = 2 일 때 최솟값(1)이므로 min= 2)
    • SWAP(list[0], list[2], temp) –> {1, 2, 5, 8, 3}
  • i = 1 일 때,
    • min = 1
    • j = 2,3,4 를 탐색하며 최솟값찾기 ( 이미 list[min] 이 최솟값임 (2))
    • SWAP() 해도 변동없음 –> {1, 2, 5, 8, 3}
  • i = 2 일 때,
    • min = 2
    • j = 3, 4 를 탐색하며 최솟값찾기 ( j = 4 일 때 최솟값(3)이므로 min=4)
    • SWAP(list[2], list[4], temp) –> {1,2,3,8,5}
  • i = 3 일 때, (마지막 i 루프)
    • min = 3
    • j = 4 탐색 ( j = 4일 때 최솟값(5)이므로 min=4)
    • SWAP(list[3], list[4], temp) –> {1,2,3,5,8}
  • 끝

Insert Sort 삽입정렬

• 인덱스 i 값보다 앞에 있는 값들이 작을 경우, 큰 값들을 뒤로 밀어서 값을 삽입할 수 있는 자리를 만들고, 인덱스 i 값 삽입하기

• 오름차순 정렬하기

  # include <stdio.h>
    
  void insertSort(int list[], int n){
      int i, j, key;
      for (i=1; i<n; i++){
          key = list[i];
            
          j = i-1;
          while (j>=0 && list[j] > key)
              list[j+1] = list[j--];  
          // j-- : 식을 모두 처리한 다음에 j -= 1
            
          list[j+1] = key;
      }
  }
  

  • 내림차순을 하고 싶다면 while 문에서 list[j] < key 로 부호를 바꿔주면 됨

    while (j>=0 && list[j] < key)
        list[j+1] = list[j--]; 
    

• EX) int list[] = {5,2,1,8,3}

  int main(){
  	int list[] = {5,2,1,8,3};
      insertSort(list, 5);
  }
  

  • i = 1 일 때,
    • key = 2
    • j = 0 : while 문 –> 5는 2보다 크니까 list[1] = list[0] –> {5,5,1,8,3}
    • j = -1 : j < 0 루프 종료, list[0] = key –> {2,5,1,8,3}
  • i = 2 일 때,
    • key = 1
    • j = 1 : while 문 –> 5는 1보다 크니까 list[2] = list[1] –> {2,5,5,8,3}
    • j = 0 : whle 문 –> 2는 1보다 크니까 list[1] = list[0] –> {2, 2, 5, 8, 3}
    • j = -1 : j < 0 루프 종료, list[0] = key –> {1,2,5,8,3}
  • i = 3 일 때,
    • 앞에 있는 값들이 모두 8 보다 작아서 변동 XX
  • i = 4 일 때,
    • key = 3
    • j = 3 : while 문 –> 8은 3보다 크니까 list[4] = list[3] –> {1,2,5,8,8}
    • j = 2 : while 문 –> 5는 3보다 크니까 list[3] = list[2] –> {1,2,5,5,8}
    • j = 1 : 2 > 3 (false) 루프 종료, list[2] = key –> {1,2,3,5,8}
  • 끝!

Bubble Sort 버블 정렬

• 앞뒤 값을 비교해서 앞에 있는 값이 크다면 뒤에있는 값과 바꾸기 SWAP SWAP SWAP !!

• 오름차순 정렬하기

  #include <stdio.h>
  #define SWAP(x,y,t) (t=x, x=y, y=t)
    
  void bubbleSort(int list[], int n) {
  	int i, j, temp;
  	for (i = 0; i < n-1; i++) {
  		for (j = 0; j < n - 1 - i; j++) {
  			if (list[j] > list[j + 1]) {
  				SWAP(list[j], list[j + 1], temp);
  			}
  		}
  	}
    
  	for (i = 0; i < n; i++)
  		printf("%d ", list[i]);
  }
  

  • 내림차순은 if (list[j] > list[j + 1])의 부호를 < 로 바꿔주면 된다

    if (list[j] < list[j + 1])
    	SWAP(list[j], list[j + 1], temp);
    

• EX) int list[] = {5,2,1,8,3}

  int main(){
  	int list[] = {5,2,1,8,3};
      bubbleSort(list, 5);
  }
  

  • i = 0 일 때,

    • j = 0, 1, 2, 3 ( j < 5 - 1 - 0)

    • j = 0 : list[0] > list[1] (5>2) true, SWAP –> {2,5,1,8,3}
    • j = 1 : list[1] > list[2] (5>1) true, SWAP –> {2,1,5,8,3}
    • j = 2 : list[2] > list[3] (5>8) false
    • j = 3 : list[3] > list[4] (8>3) true, SWAP –> {2,1,5,3,8}

  • i = 1 일 때,

    • j = 0, 1, 2 ( j < 5 -1 -1)
    • j = 0 : list[0] > list[1] (2>1) true, SWAP –> {1,2,5,3,8}
    • j = 1 : list[1] > list[2] (2>5) false
    • j = 2 : list[2] > list[3] (5>3) true, SWAP –> {1,2,3,5,8}

  • i = 2 일 때,

    • j = 0, 1 ( j < 5 -1 -2)
    • j = 0 : list[0] > list[1] (1>2) false
    • j = 1 : list[1] > list[2] (2>3) false

  • i = 3 일 때,

    • j = 0 ( j < 5 -1 -3)

• j = 0 : list[0] > list[1] (1>2) false

  • 끝!