Sort

[알고리즘] 삽입 정렬 Insertion Sort (자바/Java)

목차 삽입 정렬 0번째부터 i번째까지 정렬된 배열의 크기를 증가시키며 정렬하는 알고리즘 이미 정렬된 i개짜리 배열에 하나의 원소를 더하여 정렬된 i+1개짜리 배열 만들기! 시간 복잡도: $O(n^2)$ 과정 i번째 원소를 정렬할 차례 i-1번째까지의 원소들은 정렬되어 있음 i-1부터 0까지의 원소들과 i번째 원소(key)를 비교하며, i번째 원소보다 작은 원소를 만나면 break, i번째 원소보다 크다면 해당 원소를 오른쪽으로 한 칸씩 shift break한 원소 다음 자리에 i번째 원소를 삽입 1부터 마지막 원소까지 반복 1 0번째 원소는 정렬된 상태 i=1, 10 10..

[알고리즘] 카운팅 정렬(Counting Sort) (자바/Java)

목차 카운팅 정렬 데이터끼리 비교 없이 데이터의 개수를 세어 정렬하는 알고리즘 제한 정수나 정수로 표현할 수 있는 자료에 대해서만 한정 데이터의 입력 범위가 제한적인 경우에 효율적 데이터의 수는 적지만, 데이터 값의 범위가 큰 경우(ex. 1~10억) count 배열이 메모리를 과다하게 사용하여 비효율적! 시간복잡도 O(n+k) n: 배열의 길이 k: 정수의 최대값 과정 정렬할 배열에서 가장 큰 정수를 크기로 하는 count 배열을 선언한다.. 데이터 값이 i인 경우, count[i]를 1씩 증가시킨다. count가 모두 끝나면, 앞에서부터 누적합하여 count배열을 수정한다. 기존 배열의 맨 마지막 index부터 정렬을 시작한다. arr[n-1]이 k일 경우, count[k]의 값을 찾아, 그 값을 1..

[알고리즘] 정렬 - 선택 정렬(Selection Sort) (자바/Java)

목차 선택 정렬 개념 주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식으로 정렬하는 알고리즘 시간 복잡도: O(n^2) 정렬 과정 첫 번째 원소를 두 번째부터 마지막 원소까지 비교하여 가장 작은 값과 자리 교환 2가 가장 작은 원소이고, 그 값의 index는 2이므로 arr[0]과 arr[1] 교환, arr[0]은 가장 작은 값으로 정렬 완료 두 번째, 세 번째 … 끝에서 두 번째 원소까지 같은 과정을 반복함 코드 package sort; import java.util.Arrays; public class SelectionSort { public static void main(String[] args) { int[] arr = { 30, 15, 2, 8, 21, 7 }; ..

[알고리즘] 정렬 - 버블 정렬(Bubble Sort) (자바/Java)

목차 버블 정렬 개념 인접한 두 개의 원소를 비교하며 정렬하는 알고리즘 정렬 과정 배열이 {30, 15, 2, 8, 21, 7}일 때를 가정한다. 원소는 자신의 오른쪽 값과 비교하기 때문에, 첫 사이클에서 비교할 마지막 index는 n-2이다. n-1(마지막 원소)와 비교를 하면 한 사이클이 끝나기 때문이다. 그렇게 한 사이클이 지나면 가장 큰 값이 배열의 오른쪽에 위치하여 다음 사이클에서는 비교 대상에서 제외된다. 두 번째는 30을 제외하고 다섯개의 원소만 비교하며 같은 과정을 반복한다. 이 사이클이 끝나면 두 번째로 큰 원소인 21이 자신의 위치를 찾아간다. 이렇게 반복하다보면 i가 1일때, 두 번째로 작은 원소인 7이 정렬되고, 자동으로 가장 작은 원소인 2는 비교 대상이 없기 때문에 모든 정렬이 ..

[백준] 10814 - 나이순 정렬 (자바/Java)

문제 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다. 출력 첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다. 수업..

[백준] 10989 - 수 정렬하기 3 (자바/Java) : 계수 정렬(Counting Sort)

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 계수 정렬을 이용하는 문제이다. 처음에 입력 범위가 10,000인 걸 모르고 에러 남..하하 package BOJ0726; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.O..