[알고리즘] 알고리즘 뽀개기(4) : 정렬

알고리즘 뽀개기 Step 4 : 정렬

알고리즘을 최대한 간단하면서 빼먹는 부분이 없게 복습 및 요약하기 위해 포스팅을 하려고 합니다 :)

추천한 문제는 일부만 해설되어있으며, 언어는 Kotlin 입니다.

정렬

sort

• 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 힙 정렬, 병합 정렬 등이 존재
  • 주로 O(N^2), O(NlogN) 의 복잡도로 나뉘는데, 정렬 알고리즘은 빠를 수록 좋기 때문에, O(NlogN)이하로 걸리는 정렬을 사용하도록 한다.
• 정렬을 직접 구현하는 것보다, C++ 기준 STL 에 있는 sort (각 언어에서 구현되어있는 소팅 수단)을 사용하는 것이 좋다.
  • sort(begin, end) 로, begin 부터 end 바로 전까지를 정렬하는 함수
  • 리스트의 0~n 까지를 정렬할 경우, sort(0, n-1)
• 좌표 등과 같이 두 자료형을 합쳐서 소팅해야할 경우 Pair 등을 이용해 정렬한다
• Stable Sorting
  • 같은 것이 있는 경우, 정렬하기 전의 순서가 유지되는 정렬 알고리즘을 Stable Sorting 알고리즘이라고 한다.
  • O(NlogN)이면서, stable sorting 인 알고리즘은 병합정렬(Merge Sort)가 있다.

복습 문제

좌표 정렬하기 (11651번)

• Kotlin 의 Pair 을 사용했고, custom 으로 sort 하기 위해, comparator 를 선언해서 사용했다.코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val N = readLine().toInt()
    val arr = arrayListOf<Pair<Int, Int>>()
    for (i in 0 until N) {
        val point = readLine().split(" ")
        arr.add(Pair(point[0].toInt(), point[1].toInt()))
    }

    arr.sortWith(Comparator { o1, o2 ->
        if (o1.second == o2.second) {
            o1.first.compareTo(o2.first)
        } else {
            o1.second.compareTo(o2.second)
        }
    })

    for(pair in arr) {
        println("${pair.first} ${pair.second}")
    }
}

k번째 수(11004번)

코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val input = readLine().split(" ")
    val N = input[0].toInt()
    val K = input[1].toInt()
    val nums = readLine().split(" ")

    val arr = arrayListOf<Int>()

    for(element in nums) {
        arr.add(element.toInt())
    }

    arr.sort()

    println(arr[K-1])
}