[알고리즘] 정렬

개요

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

버블 정렬

• 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);
  		}
  	}
  }