[알고리즘] 정렬

개요

• 데이터들이 주어졌을 때 이를 정해진 순서대로 나열

버블 정렬

• n-1번째와 n번째를 정렬한 뒤 다시 처음부터 n-2번째와 n-1번째까지 정렬
• O(n^2)
• C++ code

  void bubbleSort(vector<int> &numbers) {
   for(int i = 1 ; i < (int)numbers.size() ; i++) {
       for(int j = 0 ; j < (int)numbers.size() - i ; j++) {
           if(numbers.at(j) > numbers.at(j + 1)) {
               swap(numbers.at(j), numbers.at(j + 1));
           }
       }
   }
  }
  

칵테일/셰이커 정렬

• 홀수 번째 돌 때는 앞부터, 짝수 번째는 뒤부터 훑는 정렬
• O(n^2)
• C++ code

  void cocktailSort(vector<int> &numbers) {
   for(int i = 1 ; i < (int)numbers.size() ; i++) {
       if(i % 2 == 1) {
           for(int j = 0 ; j < (int)numbers.size() - i ; j++) {
               if(numbers.at(j) > numbers.at(j + 1)) {
                   swap(numbers.at(j), numbers.at(j + 1));
               }
           }
       } else {
           for(int j = numbers.size() - i ; j > 0 ; j--) {
               if(numbers.at(j - 1) > numbers.at(j)) {
                   swap(numbers.at(j), numbers.at(j - 1));
               }
           }
       }
   }			
  }
  

선택 정렬

• 1번째부터 끝까지 훑어서 가장 작은 게 1번째, 2번째부터 끝까지 훑어서 가장 작은 게 2번째를 반복하는 정렬
• O(n^2)
• C++ code

  void selectionSort(vector<int> &numbers) {
   for(int i = 0 ; i < (int)numbers.size() - 1; i++) {
       int min = i;
       for(int j = i + 1 ; j < (int)numbers.size() ; j++) {
           if(numbers.at(i) > numbers.at(j)) {
               min = j;
           }
       }
  
       if(i != min) {
           swap(numbers.at(i), numbers.at(min));
       }
   }
  }
  

이중 선택 정렬

• 끝까지 훑어서 최솟값과 최댓값을 동시에 찾아낸 뒤 값을 바꾼 다음 훑는 범위를 양쪽으로 한 칸씩 줄여서 반복하는 정렬
• O(n^2)
• C++ code

  void doubleSelectionSort(vector<int> &numbers) {
   for(int i = 0 ; i < (int)numbers.size() - i; i++) {
       int start = i;
       int end = (int)numbers.size() - i - 1;
  
       int min = start;
       int max = end;
       for(int j = start ; j <= end ; j++) {
           if(numbers.at(j) < numbers.at(min)) {
               min = j;
           } else if(numbers.at(j) > numbers.at(max)) {
               max = j;
           }
       }
  
       if(start != min) {
           swap(numbers.at(start), numbers.at(min));
  
           if(start == max) {
               max = min;
           }
       }
  
       if(end != max) {
           swap(numbers.at(end), numbers.at(max));
           break;
       }
   }
  }
  

삽입 정렬

• k번째 원소를 1부터 k-1까지와 비교해 적절한 위치에 끼워넣고 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 정렬
• O(n^2)
• C++ code

  void insertionSort(vector<int> &numbers) {
   for(int i = 0 ; i < (int)numbers.size() - 1 ; i++) {
       for(int j = i + 1 ; j >= 0 && numbers[j - 1] > numbers[j] ; j--) {
           swap(numbers.at(j - 1), numbers.at(j));
       }
   }
  }
  

병합/합병 정렬

• 원소 개수가 1 또는 0이 될 때까지 두 부분으로 쪼개고 쪼개서 자른 순서의 역순으로 크기를 비교해 병합해가는 정렬
• 안전한 정렬
• O(n log n)
• C++ code

  void mergeSort(vector<int> &numbers, const int &start, const int &end) {
   if(start >= end) {
       return;
   }
  
   int middle = (start + end) / 2;
  
   mergeSort(numbers, start, middle);
   mergeSort(numbers, middle + 1, end);
  
   vector<int> temp;
   temp.clear();
   int i = start, j = middle + 1;
   while(i <= middle && j <= end) {
       if(numbers.at(i) < numbers.at(j)) {
           temp.push_back(numbers.at(i++));
       } else {
           temp.push_back(numbers.at(j++));
       }
   }
  
   while(i <= middle) {
       temp.push_back(numbers.at(i++));
   }
  
   while(j <= end) {
       temp.push_back(numbers.at(j++));
   }
  
   for(int i = start ; i <= end ; i++) {
       swap(numbers.at(i), temp.at(i - start));
   }
  }
  

힙 정렬

• 힙을 이용하여 정렬
• O(n log n)

퀵 정렬

• 원소 하나를 피봇으로 잡고 피봇을 기준으로 피봇보다 큰 값, 작은 값으로 나눈뒤 각각에 대해 다시 피봇을 잡아 나누어가는 정렬
• O(n log n)
• C++ code

  void quickSort(vector<int> &numbers, const int &left, const int &right) {
   if(left >= right) {
       return;
   }
  
   int pivot = (left + right) / 2;
  
   int leftArrow = left;
   int rightArrow = right;
   bool leftDirection = true;
  
   while(leftArrow <= rightArrow) {
       if(leftDirection) {
           if(numbers.at(leftArrow) >= numbers.at(pivot)) {
               swap(numbers.at(leftArrow), numbers.at(pivot));
               pivot = leftArrow;
           }
           ++leftArrow;
           leftDirection = false;
       } else {
           if(numbers.at(rightArrow) <= numbers.at(pivot)) {
               swap(numbers.at(rightArrow), numbers.at(pivot));
               pivot = rightArrow;
           }
           --rightArrow;
           leftDirection = true;
       }
   }
  
   quickSort(numbers, left, pivot - 1);
   quickSort(numbers, pivot + 1, right);
  }
  

트리 정렬

• 이진 탐색 트리를 만들어 정렬하는 방식
• O(n log n)

카운팅 정렬

• 각 항목의 개수를 이용하여 정렬하는 방식
• 배열을 이용하므로 정수인 자료만 가능
• 데이터의 최대값이 작다면 매우 효율적인 알고리즘
• O(n + k)
  • k는 데이터의 최대값
• C++ code

  void countingSort(vector<int> &numbers, const int maxSize) {
   vector<int> counting(maxSize + 1);
  
   for(auto &iter : numbers) {
       counting[iter]++;
   }
  
   numbers.clear();
   for(int i = 0 ; i < (int)counting.size() ; i++) {
       if(counting.at(i) == 0) {
           continue;
       }
  
       for(int j = 0 ; j < counting.at(i) ; j++) {
           numbers.push_back(i);
       }
   }
  }