기초 정렬 알고리즘

💡 정렬 알고리즘이란? N개의 숫자가 입력으로 주어졌을 때, 사용자가 지정한 기준에 맞게 정렬해 출력하는 알고리즘이다.

선택 정렬(Selection Sort)

• 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다.
• 현재 위치에 저장될 값의 크기가 작냐, 크냐에 따라 최소 선택정렬과 최대 선택정렬로 구분할 수 있다.
• 최소 선택정렬: 오름차순
• 최대 선택정렬: 내림차순
• 로직(오름차순)
  1. 정렬되지 않은 인덱스의 맨 앞부터, 이를 포함한 배열 값 중 가장 작은 값 찾기
  2. 가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꿔준다.
  3. 다음 인덱스부터 반복한다.
• 시작 복잡도는 O(n^2)
• 공간 복잡도는 하나의 배열에서만 진행하므로 O(n)

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

삽입 정렬(Insertion Sort)

• 삽입 정렬은 현재 위치에서 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아, 그 위치에 삽입하는 배열 알고리즘
• 로직
  1. 삽입 정렬은 두번째 인덱스부터 시작한다. 현재 인덱스는 별도의 변수에 저장하고, 비교 인덱스를 현재 인덱스의 -1로 잡는다.
  2. 별도로 저장한 변수와 비교 인덱스의 배열 값을 비교한다.
  3. 삽입 변수의 값이 작으면 현재 인덱스로 비교 인덱스의 값을 저장, 비교 인덱스를 -1로 해 비교를 반복한다.
  4. 만약 삽입 변수가 더 크면, 비교 인덱스+1에 삽입 변수를 저장한다.
• 시간 복잡도는 역 정렬된 경우 O(n^2)이지만, 정렬된 경우 한번만 비교해 O(n)이 올 수 있다.
• 공간 복잡도는 단 하나의 배열에서 진행해 O(n)

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

버블 정렬(Bubble Sort)

• 매번 연속된 두개 인덱스를 비교해, 정한 기준의 값을 뒤로 넘겨 정렬하는 방법
• 오름차순으로 정렬하고자 할 때, 비교시마다 큰 값이 뒤로 이동해, 1바퀴 돌면 가장 큰 값이 맨 뒤에 저장된다.
• 맨 마지막에는 비교하는 수들 중 가장 큰 값이 저장되기 때문에, “전체 배열 크기 - 현재 순환 바퀴 수” 만큼 반복한다.
• 로직
  1. 두번째 인덱스부터 시작한다. 현재 인덱스 값과 -1한 이전의 인덱스 값을 비교한다.
  2. 이전 인덱스가 크다면, 현재 인덱스와 변경
  3. 현재 인덱스가 크면, 변경없이 다음 연속된 두 값을 비교한다.
  4. 전체 배열 크기 - 순환 횟수만큼 반복
• 전체 비교를 진행하므로 시간 복잡도는 O(n^2)
• 공간 복잡도는 하나의 배열에서 진행하므로 O(n)

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

[참고]

• https://hsp1116.tistory.com/33
• https://liveyourit.tistory.com/220
• 추가 정렬: https://reakwon.tistory.com/37