Sort - (1) Bubble, Selection, Insertion, Shell

• Bubble sort
  • 인접한 두 개의 원소를 비교하며 자리를 바꾸는 방식

  void bubbleSort(int arr[], int length) {
      
      for(int i = 0; i < length; i++) {
          for(int j = 0; j < length - i -1; j++)
              if(arr[j] > arr[j+1]) swap(&arr[j], &arr[j+1]);
      }
      
  }
  

• Selection Sort
  • 가장 작은 원소를 찾아서 맨 앞부터 자리를 바꾸는 방식

  void selectionSort(int arr[], int length) {
      
      for(int i = 0; i < length - 1; i++) {
          int min = i;
          for(int j = i + 1; j < length; j++)
              if(arr[min] > arr[j]) min = j;
          swap(&arr[i], &arr[min]);
      }
      
  }
  

• Insertion Sort
  • 정렬된 집합과 정렬되지 않은 집합을 나눈 후, 정렬되지 않은 집합의 원소를 차례로 정렬된 집합에 적합한 위치에 삽입하는 방식
  • 초기 배열이 '거의 정렬'되어 있을 경우 효율적

  void insertionSort(int arr[], int length) {    
  		for(int i = 1; i < length; i++) {
          int value = arr[i], pos = i;
          
          while(pos > 0 && value < arr[pos-1]) {
              arr[pos] = arr[pos-1];
              pos--;
          }
          arr[pos] = value;
      }
  }
  

• Shell Sort
  • 일정한 간격(interval)로 떨어진 부분 집합에 대해서 삽입 정렬을 반복 수행한다. 전체 원소에 대해서 수행하는 것보다 집합의 크기를 작게 하여 비교 연산과 교환 연산을 적게 발생하도록 하려고 고안된 방식이다

  void InsertionSort(int arr[], int begin, int end) {
      
      for(int i = begin + 1; i < end; i++) {
          int value = arr[i], j = i;
          
          while(j > 0 && value < arr[j-1]) {
              arr[j] = arr[j-1];
              j--;
          }
          arr[j] = value;
      }
      
  }
  
  void ShellSort(int arr[], int length) {
      int interval = length / 2;
      
      while (interval > 0) {
          for(int i = 0; i < length; i+=interval) {
              int sub_length = i + interval > length ? length : i + interval;
              InsertionSort(arr, i, sub_length);
          }
          interval /= 2;
      }
  }