1차원 배열(복습)
같은 자료형의 데이터를 연속된 메모리 공간에 저장하는 선형 자료구조
배열의 생성(초기화)
int[] arr = new int[5];
선언과 동시에 값 지정
int[] array = {1, 2, 3, 4, 5};
시간 복잡도
- 접근 및 수정 O(1) : 인덱스를 통해 즉시 접근 가능
Ex) arr[2] - 검색 O(N) : 원하는 값을 찾기 위해 처음부터 끝까지 확인 가능
- 삽입/삭제 O(N) : 중간에 데이터를 넣거나 뺄 때 나머지 요소 이동
cf) 배열과 연결 리스트의 차이
정렬(Sort)
- 데이터(숫자, 문자, 객체 등)들을 일정한 규칙(오름차순, 내림차순 등)에 따라 순서대로 재배열 하는것을 말함
- 다양한 알고리즘에서 선행 작업으로 활용되기도 함(데이터 처리 속도 향상)
- 자바에서는 Arrays 클래스와 Collections 클래스에서 sort()메서드를 지원함
버블 정렬(Bubble Sort)
- 인접한 두 개의 원소를 비교하여 크기가 순서에 맞지 않는다면 서로 교환(Swap)하는 과정을 반복하여 정렬하는 알고리즘
- 한번의 사이클이 끝날 때 마다 가장 큰(또는 작은) 원소가 끝에 위치하게 되는 모습이 거품이 올라오는 것과 유사하다고 하여 '버블 정렬(Bubble Sort)라고 부름
- 시간 복잡도 : O(N2)
버블 정렬 과정
- 배열의 처음부터 끝까지 인접 원소를 짝지어 비교
- 비교한 두 원소의 순서가 잘못되어 있자다면 교환(Swap)-> 오름차순, 내림차순
- 한 사이클이 끝나면 배열의 마지막 인덱스에 가장 큰(작은) 원소가 위치
- 범위를 줄여 나가며 N-1번 정도 반복 수행하면 정렬 완료Í‹››
구현예시 : Java
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] arr = { 1, 16, 2, 20, 97, 99 };
int N = arr.length;
// array의 길이를 저장
for (int i = N - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
// 오름차순 정렬
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
System.out.println(Arrays.toString(arr));
}
}
}선택 정렬(Selection Sort)
- 정렬되어 있지 않은 배열 혹은 리스트에서 가장 작은(또는 가장 큰) 원소를 찾아 맨 앞(또는 맨 뒤)으로 옮기는 과정을 반복하여 전체를 정렬하는 과정
- 시간 복잡도 : O(N2)
선택 정렬 과정
- 주어진 리스트 중에서 최솟값을 찾는다
- 맨 앞의 원소와 가장 작은 값을 swap한다
- 맨 앞의 원소를 제외한 나머지 구간에 반복 수행한다
구현예시 : Java
import java.util.Arrays;
public class SelectionSort {
public static void main(String[] args) {
int[] arr = { 1, 16, 2, 20, 97, 99 };
int N = arr.length;
for (int i = 0; i < N - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < N; j++) {
if (arr[minIdx] > arr[j]) {
minIdx = j;
}
}
// if(minIdx == i) continue;
int tmp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = tmp;
}
System.out.println(Arrays.toString(arr));
}
}
안정 vs 불안정 정렬 차이 : 중복된 값이 있을 때, 입력된 순서가 정렬 후에도 유지되는 가?
버블 정렬 : 인접한 수만 바꾸고 값이 같으면 바꾸지 않고 지나감
선택 정렬 : 수에 따라 변경이 될 수 있음
ex) 2 (a), 2(b), 1 -> 1, 2 (b), 2 (a) : 맨 앞에 있는 2(A)와 1을 바꾸면서 순서 역전
카운팅 정렬(Counting Sort)
각 항목이 몇 번 등장했는지(빈도)를 세서, 그 정보를 이용해 정렬 결과를 만든다.
→ 비교 기반 정렬이 아니라 카운트 기반 정렬이라 선형 시간에 가깝게 가능
특징
(1) 안정 정렬(Stable)로 구현 가능: 같은 값의 원래 순서 유지
(2) 정수(또는 정수로 매핑 가능한 값)에 대해서만 적용하기 쉬움
(값 자체를 인덱스로 쓰는 count 배열을 만들기 때문)
(3) 비 비교 정렬
조건 / 제약
(1) count[value] 형태로 쓰려면 값의 범위(최대값)를 알아야 한다.
(2) 값의 최대가 크면 count 배열이 커져서 공간 사용량이 증가한다.
시간 복잡도
O(n + k)
- n : 입력 데이터(배열) 길이
-> 배열을 돌면서 각 숫자가 몇 번 나왔나 세기 : O(n) (1단계)
-> 2단계 수행후 원래 배열을 한 번 더 탐색 : O(n) (3단계) - k : 값의 범위(최대값 규모)
-> 0부터 k까지 돌면서 누적합 계산 : O(k)(2단계)
따라서, O(2n+k) = O(n+k)
카운팅 정렬의 과정
(1) 데이터가 들어갈 수 있는 범위 확인
cf) 데이터 범위가 항상 0부터 시작한다는 보장은 없음
(2) 0~k (데이터 범위)까지의 배열 생성
(3) 데이터를 순회하면서 해당 인덱스의 값을 증가시킴
(4) 카운트 배열의 누적합을 구하여 정렬된 결과를 어느 위치에 배치해야하는 지 알 수 있음
(5) 원본 배열의 뒤에서부터 순회하며 원소를 배치
구현예시 : Java
public static int[] countingSort(int[] arr) {
int N = arr.length;
// 1. 가장 큰 값 찾기
int K = -1;
for (int i = 0; i < N; i++) {
if (arr[i] > K) K = arr[i];
}
// 2. Counting 하기
// 등장 횟수를 저장할 count 배열 생성
int[] count = new int[K + 1];
// 각 숫자 등장 횟수 세기
for (int i = 0; i < N; i++) {
count[arr[i]]++;
}
// 3. 누적합 구하기
for (int i = 1; i < K + 1; i++) {
count[i] += count[i - 1]; // count[i] → i 이하의 숫자가 총 몇 개인지
}
// 4. 역방향으로 원본을 순회하면서 정렬 시작
int[] sortedArr = new int[N]; // 원본 배열과 동일한 크기의 배열
for (int i = N - 1; i >= 0; i--) // 뒤에서부터 순회
{
int num = arr[i]; // 현재 정렬 대상 값
int idx = count[num] - 1; // 누적합 정보로 실제 들어갈 인덱스 계산
sortedArr[idx] = num; // 계산된 위치에 값 저장
count[num]--; // 다음 동일 숫자가 앞에 올 수 있도록 위치 한 칸 전진
}
return sortedArr;
}
}
기수 정렬(Radix Sort)
원소끼리 a < b 비교를 반복하는 대신, 자릿수(digit) 를 기준으로 여러 번 분류/정렬을 반복해 전체를 정렬하는 알고리즘
-> 보통 각 자릿수 정렬 단계에서 카운팅 정렬 같은 안정 정렬을 사용함
정렬 방식 (LSD 방식)
1의 자리 → 10의 자리 → 100의 자리 → … 순서로 정렬(Least Significant Digit)
특징
(1) 안정 정렬(Stable) 로 구현 가능(자릿수별 정렬이 안정적이면 전체도 안정적)
(2) 주로 0 이상의 정수 정렬에 많이 사용
(3) 정수뿐 아니라 자릿수 개념으로 표현 가능한 문자열에도 응용 가능
시간 복잡도
O(d × (n + k))
- n: 데이터 개수(배열 길이)
- d: 자릿수 개수
- k: 한 자릿수의 값 범위(10진수면 0~9라서 보통 k=10)
-> 카운팅 정렬 O(n+k)를 자릿수 d번 반복하는 것과 같음
-> d가 커질수록(자릿수 많을수록) 느려짐
제약/주의
(1) 자릿수가 늘면 비용 증가
(2) 음수 / 소수는 그대로 적용하기 어렵고, 처리하려면 추가 변환/전처리가 필요함
구현예시 : Java
// 기수정렬(LSD방식)
public static void radixSort(int[] arr) {
// 최댓값 찾기(자릿수 계산)
int max = arr[0];
for (int v : arr) {
if (v > max) max = v;
}
// 1의 자리, 10의자리, 100의자리.... 정렬
// 가장 큰수의 자릿수까지만 정렬 ( ex 123 /1000 = 0 되어서 종료)
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, exp); } }
public static void countingSort(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n]; // 자릿수 정렬이 완료된 데이터 임시 보관
int[] count = new int[10]; // 자릿수별로 비교, 올 수 있는 숫자는 0-9
// 1. 개수 세기
for (int i = 0; i < n; i++) {
int digit = (arr[i] / exp) % 10; // 전체값이 아니라 특정 자릿수만 추출
count[digit]++; }
// 2. 누적합
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1]; }
// 3. 역방향으로
for (int i = n - 1; i >= 0; i--) {
int digit = (arr[i] / exp) % 10; //자릿수 추출
output[count[digit] - 1] = arr[i]; //자릿수 기준 위치에 저장
count[digit]--; }
// 4. output arr에 덮기
// 새 배열에 반환하는 카운팅과 달리 다음 자릿수 정렬을 위해 원본 배열 업데이트
for (int i = 0; i < n; i++) {
arr[i] = output[i]; } } }
열심히 이 글을 읽으시고, 코딩체력이 높으신 분들은 당연하게
Arrays.sort() 쓰면 되는 거 아님?
이라는 생각을 하셨을 것이다.
cf) Arrays.sort()
java.util.Arrays의 sort()는 배열을 정렬하는 표준 메서드
- 대표형태
Arrays.sort(int[] a); // 기본형(primitive) 배열
Arrays.sort(Integer[] a); // 객체 배열(Wrapper)
Arrays.sort(T[] a, Comparator<? super T> c); // 비교기(정렬 기준) 지정
Arrays.sort(a, from, to); // 부분 정렬(1) 기본형 배열
Ex) int[], double[]
- Dual-Pivot Quicksort 계열을 사용
- 평균적으로 빠르고 상수항이 작음
- 안정 정렬(stable) X
- 시간복잡도: 평균 O(n log n)
int[] a = {5, 2, 9, 1};
Arrays.sort(a);(2) 객체 배열
Ex) Integer[], String[] etc
- TimSort(MergeSort 계열, “runs” 활용) 사용
- 안정 정렬(stable)
→ 같은 값(비교 결과 0)이면 원래 순서가 유지됨 - 시간복잡도: O(nlogn)
- 부분적으로 이미 정렬된 데이터에 강함
String[] s = {"b", "a", "a"};
Arrays.sort(s); // stable: 같은 "a"의 상대 순서 유지대부분의 코테/실무 정렬은 Arrays.sort()로 충분..!
샤라웃 투 ㅅㅇ
땡스 투 ㅅㅎ
