๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์ฝ”๋”ฉํ…Œ์ŠคํŠธ/๊ธฐ๋ณธ ์•Œ๊ณ ๋ฆฌ์ฆ˜

์ •๋ ฌ ์ฝ”๋“œ1(๊ณ„์ˆ˜ ์ •๋ ฌ, ์‚ฝ์ž… ์ •๋ ฌ, ์„ ํƒ ์ •๋ ฌ)

๊ณ„์ˆ˜ ์ •๋ ฌ (count sort)

  • ๊ณ„์ˆ˜์ •๋ ฌ์€ ๋ฐ์ดํ„ฐ์˜ ํฌ๊ธฐ ๋ฒ”์œ„๊ฐ€ ์ œํ•œ๋˜์–ด ์ •์ˆ˜ํ˜•ํƒœ๋กœ ํ‘œํ˜„๋  ์ˆ˜ ์žˆ์„๋•Œ ํšจ๊ณผ์ ์œผ๋กœ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค. (์ผ๋ฐ˜์ ์œผ๋กœ ํฐ ๋ฐ์ดํ„ฐ์™€ ์ž‘์€ ๋ฐ์ดํ„ฐ์˜ ์ฐจ์ด๊ฐ€ 1,000,000์ด ๋„˜์ง€ ์•Š์„๋•Œ ์‚ฌ์šฉํ•œ๋‹ค.)
  • ๋ฐ์ดํ„ฐ์˜ ๊ฐœ์ˆ˜๊ฐ€ N, ๋ฐ์ดํ„ฐ ์ค‘ ์ตœ๋Œ€๊ฐ’์ด K์ผ๋•Œ, ์ตœ์•…์˜ ๊ฒฝ์šฐ์—๋„ O(n+k)์˜ ์ˆ˜ํ–‰์‹œ๊ฐ„์„ ๋ณด์žฅํ•˜๋Š” ๋น ๋ฅธ ์ •๋ ฌ๋ฒ•์ด๋‹ค.
  • ๋™์ž‘์›๋ฆฌ๋Š” ๋งŒ์•ฝ ์ตœ์†Œ0๋ถ€ํ„ฐ ์ตœ๋Œ€1,000,000์˜ ๋ฐ์ดํ„ฐ๊ฐ€ ์ฃผ์–ด์ง€๋Š” ๊ฒฝ์šฐ, '๋ชจ๋“  ๋ฒ”์œ„๋ฅผ ๋‹ด์„ ์ˆ˜ ์žˆ๋Š” ๋ฆฌ์ŠคํŠธ' - ์ฆ‰ 1,000,001๊ฐœ์˜ ๋ฆฌ์ŠคํŠธ๋ฅผ ์„ ์–ธํ•˜์—ฌ ๊ฐ ๊ฐ’์„ ๋‹ด๋Š”๊ฒƒ์ด๋‹ค. ๊ทธ๋ž˜์„œ ๋งค์šฐ ํฐ ๋ฒ”์œ„๋Š” ์‚ฌ์šฉํ•  ์ˆ˜ ์—†๋‹ค.

def count_sort(array):

    count = [0] * (max(array) + 1)

 

    for i in range(len(array)):

        count[array[i]] += 1         # (array[0] = 7) => count[7] += 1

 

    for i in range(len(count)):

        for _ in range(count[i]):     # count[1]๊ฐ€ ๋งŒ์•ฝ 3์ด๋ผ๋ฉด 1์„ 3๋ฒˆ ๋ฐ˜๋ณตํ•˜์—ฌ

            print(i, end=' ')            # 1 1 1 ์ด๋ผ๋Š” ์ถœ๋ ฅ์„ ํ•œ๋‹ค.


์‚ฝ์ž… ์ •๋ ฌ (insertion sort)

  • ํ‰๊ท ์ ์œผ๋กœ O(n^2)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง€์ง€๋งŒ ํ˜„์žฌ ๋ฐ์ดํ„ฐ ๋ฆฌ์ŠคํŠธ๊ฐ€ ๊ฑฐ์˜ ์ •๋ ฌ๋œ ์ƒํƒœ์ผ๋•Œ ์ตœ๋Œ€ O(n)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค.
  • ์ฆ‰, ์ฃผ์–ด์ง„ ๋ฐ์ดํ„ฐ๊ฐ€ ๊ฑฐ์˜ ์ •๋ ฌ๋œ ์ƒํƒœ๋ผ๋ฉด ํ€ต์ •๋ ฌ๋ณด๋‹ค ๋” ํšจ์œจ์ ์ด๋ฏ€๋กœ ๋ฐ์ดํ„ฐ์˜ ์ƒํƒœ๋ฅผ ๋ณด๊ณ  ์‚ฌ์šฉํ•˜๋ฉด ํšจ๊ณผ์ ์ด๋‹ค.

def insertion_sort(array):

    for i in range(1, len(array)):    

        for j in range(i, 0, -1):

            if array[j] < array[j - 1]:

                array[j], array[j - 1] = array[j - 1], array[j]      # ๋งŒ์•ฝ array[i]๋ณด๋‹ค array[i-1]์ด ํฌ๋‹ค๋ฉด ๋‘ ์ธ๋ฑ์Šค ์Šค์™‘

            else: break

    return(array)


์„ ํƒ ์ •๋ ฌ (selection sort)

  • ์ง๊ด€์ ์ด์ง€๋งŒ O(n^2)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ ธ ๋งค์šฐ ๋Š๋ฆฌ๋ฏ€๋กœ ์‚ฌ์šฉํ•  ์ผ์€ ์ ๋‹ค.
  • ์ •๋ ฌ์˜ ๊ธฐ๋ณธ ์ฝ”๋“œ๋กœ ์ง„ํ–‰ ๋ฐฉ์‹์„ ์ดํ•ดํ•˜๊ธฐ ์ข‹์€ ์ฝ”๋“œ์ด๋‹ค.

 


def selection_sort(array):

    for i in range(len(array)):

        min_index = i

        for j in range(i + 1, len(array)):

            if(array[min_index] > array[j]):

                min_index = j

        array[i], array[min_index] = array[min_index], array[i]

    return(array)