Algorithm
[알고리즘]정렬
이수밈
2023. 8. 13. 21:49
버블 정렬
- 버블정렬 : 인접한 두개의 원소를 비교하며 자리를 계속 교환하는 방식 (오름차순 기준)
- 정렬과정
- 첫번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동한다
- 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다.
- 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 하여 버블 정렬이라고 한다.
- 원소가 N개인 배열을 정렬하려고 했을 때, N-1번의 사이클을 돌면 된다!
- 시간 복잡도 : O(n^2)
import java.util.Arrays;
public class Array1_03_BubbleSort {
public static void main(String[] args) {
// 오름차순 기준 정렬
int[] nums = { 24, 99999, 99, 31, 213124, 7, 35 };
int N = nums.length; // 7
// 사이클 횟수를 위한 반복문
for (int i = 0; i < N - 1; i++) {
//조건에 N-i-1을 넣으니까 이상하게 정렬함
for (int j = 1; j < N - i; j++) {
//오름차순이니까 이렇게 코드 작성
if(nums[j-1]>nums[j]) {
int tmp = nums[j];
nums[j] = nums[j-1];
nums[j-1] = tmp; //임시변수 tmp
}
} // 비교하는 반복문
}
System.out.println(Arrays.toString(nums));
}
}선택정렬
- 셀렉션 알고리즘
- 저장되어있는 자료로부터 k번째로 큰 혹은 작은 원소를 찾는 방법
- 최소값,최대값,중간값을 찾는 알고리즘을 의미함
- 선택과정
- 정렬알고리즘을 이용하여 자료 정렬하기
- 원하는 순서에 있는 원소 가져오기
- 선택정렬
- 주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식
- 스왑은 한 사이클당 한번만 일어난다.
- n-1번의 사이클을 돔
- 정렬과정
- 주어진 리스트 중에서 최소값을 찾는다
- 그 값을 리스트의 맨 앞에 위치한 값과 교환한다
- 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위의 과정을 반복한다
- 시간복잡도 O(n^2)
import java.util.Arrays;
public class Array3_03_SelectionSort {
public static void main(String[] args) {
int[] nums = { 64, 25, 10, 22, 11 };
int N = nums.length; // nums의 총 길이
// 몇 사이클을 돌아야 하는 가. 한 사이클이 종료가 될 때마다 하나씩 정렬이 되므로 n-1번
// i번째의 자리를 정렬하고자 함
for (int i = 0; i < N - 1; i++) {
int minIdx = i; // i번째 자리가 가장 작은 값이라고 초기화를 시켜둔 상태
// i이후에 등장하는 친구들과 비교하여 갱신을 해야함
for (int j = i + 1; j < N; j++) {
// 현재 내가 보고 있는 j번째 값이 minIdx값보다 작다면
if (nums[j] < nums[minIdx]) {
minIdx = j;
}
}
// 여기까지 왔다면 최소값을 가리키는 idx는 확보한 상태
if(minIdx != i) {
int tmp = nums[i];
nums[i] = nums[minIdx];
nums[minIdx] = tmp;
}
}
System.out.println(Arrays.toString(nums));
}
}
카운팅 정렬
- 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘
- 제한 사항
- 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능
- 각 항목의 발생회수를 기록하기 위해 정수 항목으로 인덱스 되는 카운트들의 배열을 사용하기 때문이다. (빈도수 구하기)
- 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야한다.
- count = new int[k+1];를 통해 카운팅 개수 파악
- count 정렬의 누적합에서 깎아가면서 배열 재정렬
- 뒤에서 부터 하는 이유: 안정정렬→ 중복된 값에 대해서 원래 순서를 유지
- 시간복잡도 : O(n+k) : n은 배열의 길이, k는 정수의 최대값 → 선형시간(1차원) → O(n)
import java.util.Arrays;
public class Array2_04_CountingSort {
public static void main(String[] args) {
// 양수를 가정하겠다.
int[] arr = { 8, 8, 24, 12, 19, 3, 45, 60 };
int N = arr.length;
// 1. 데이터 중 가장 큰 값을 알고있어야 한다.
int K = -1;
for (int i = 0; i < N; i++) {
if (K < arr[i])
K = arr[i];
} // 가장 최대값을 찾는 for
int[] count = new int[K + 1]; // 0~60 : 61칸짜리 만들어진다.
// 2. 개수 카운팅
for (int i = 0; i < N; i++) {
// arr[i] //해당 값을 인덱스로 하여 카운트를 증가시킴
count[arr[i]]++;
// 헷갈리면 아래방식
// int idx = arr[i];
// count[idx]++;
}
// 3. 누적합을 구한다(얘를 구함으로써 들어갈 수 있는 위치가 결정되고 안정정렬 가넝하게 만들어줌)
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
// 4. 원본배열의 뒤에서부터 순회를 하며 정렬된 배열에 차곡차곡 저장한다.
int[] sortArr = new int[N]; //저장할 배열을 만들어준다.
for (int i = N - 1; i >= 0; i--) {
// 지금 저장하고 싶은 값 : arr[i]
// 저장하고 싶은 위치는 어디? : count[arr[i]]-1 -> 하고나서 한 번 더 count[arr[i]]--;
// --count[arr[i]]
//i번째 원소를 인덱스로 하는 count 배열을 1 감소시킨 뒤 count 배열의 값을 인덱스로 하여 sortArr 에 value 값을 저장한다
int value = arr[i];
count[value]--;
sortArr[count[value]] = value;
// sortArr[--count[arr[i]]] = arr[i];-> 위에 식을 합친 거.
}
System.out.println(Arrays.toString(sortArr));
}
}- 복수의 원소를 카운팅 정렬하는 경우 : 마지막 원소를 기준으로 한 정렬이 우선된다. 그리고 카운팅 정렬 두번 해야함.