자료구조/알고리즘 - Bubblesort, Selectionsort, Insertionsort

정렬?

엑셀이나 문서작성 프로그램을 사용한 사람이라면 데이터를 오름차순 혹은 내림차순으로 정렬 해본적이 있을 것이다.
정렬이란 데이터의 집합을 어떠한 기준(핵심항목, key)으로 기준의 최소값이면 최대값까지 최대값이면 최소값까지 일정한 순서로 줄지어 세우는 것이다.

[4, 6, 2, 9, 1] # 정렬되지 않은 배열
[1, 2, 4, 6, 9] # 오름차순으로 정렬된 배열!
[9, 6, 4, 2, 1] # 내림차순으로 정렬된 배열!

버블정렬?

버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.

버블정렬

소스코드

def bubble(lst):

    for i in range(len(lst)):
        for j in range(len(lst)-1-i):
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]

# print(bubble([4, 6, 2, 9, 1]))
# result = [1, 2, 4, 6, 9]

선택정렬?

선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.
1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회전에서는 두 번째 자료를 가지고 비교한다. 마찬가지로 3회전에서는 세 번째 자료를 정렬한다.

선택정렬

소스코드

def selection(lst):

    for i in range(len(lst)):
        min = i
        for j in range(i+1, len(lst)):
            if lst[min] > lst[j]:
                min = j
        if min != i:
            lst[min], lst[i] = lst[i], lst[min]

    return lst
   
# print(bubble([4, 6, 2, 9, 1]))
# result = [1, 2, 4, 6, 9]

삽입정렬?

삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.
즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.

삽입정렬

소스코드

def insertion(lst):
    for i in range(1, len(lst)):
        for j in range(1, i+1):
            cur = i-j
            if lst[cur] > lst[cur+1]:
                lst[cur], lst[cur+1] = lst[cur+1], lst[cur]
            else:
                break

    return lst

# print(insertion([4, 6, 2, 9, 1]))
# result = [1, 2, 4, 6, 9]

파이썬 기본정렬, 정렬 커스텀 하기

기본 정렬 - 오름차순

nums1 = [4, 2, 5, 3, 1]
# 기본 오름차순 정렬
nums1.sort()
print(nums1)


#[1, 2, 3, 4, 5]

기본 정렬 - 내림차순

nums1 = [4, 2, 5, 3, 1]
# 내림차순
nums1.sort(reverse=True)
print(nums1)


#[5, 4, 3, 2, 1]

기본 정렬 - 반환형, 오름차순

nums2 = [4, 2, 5, 3, 1]
print(sorted(nums2))

#[1, 2, 3, 4, 5]

람다식을 이용한 정렬

students = [("John", 70), ("Mike", 60), ("Andrew", 80)]

# students에 있는 값에 0번째 거를 기준으로 정렬
print(sorted(students, key=lambda x: x[0]))

# students에 있는 값에 1번째 거를 기준으로 정렬
print(sorted(students, key=lambda x: x[1]))


# [('Andrew', 80), ('John', 70), ('Mike', 60)]
# [('Mike', 60), ('John', 70), ('Andrew', 80)]

# 'sort()' 마찬가지로 가능함.

키를 반환하는 함수를 정의하는 방법

students = [("John", 70), ("Mike", 60), ("Andrew", 80)]

# 정렬에 사용할 키를 반환하는 함수를 정의하여 정렬하는 방법
def getKey(e):
    return e[1]

print(sorted(students, key=getKey))

# [('Mike', 60), ('John', 70), ('Andrew', 80)]

키를 반환하는 함수를 정의하는 방법

from functools import cmp_to_key

students = [("John", 70), ("Mike", 60), ("Andrew", 80)]

#학생의 앞에있는 값인 이름중에 이름의 마지막에 있는 알파벳 순서대로 비교
#따라서 e가 가장 우선순위가 높고 그다음 n 그다음 w 이다.
def comparator_by_name(a, b):
    if a[0][-1] > b[0][-1]:
        return 1
    else:
        return -1

# cmp_to_key()를 사용하여 이름 기준으로 오름차순 정렬
students = [("John", 70), ("Mike", 60), ("Andrew", 80)]
print(sorted(students, key=cmp_to_key(comparator_by_name)))



#결과 : [('Mike', 60), ('John', 70), ('Andrew', 80)]

zip() 함수 사용법

zip() 함수를 활용하면 여러 그룹의 데이터를 루프를 한 번만 돌면서 처리할 수 있는데요. 가변 인자를 받기 때문에 2개 이상의 인자를 넘겨서 병렬 처리를 할 수 있습니다.

numbers = [1, 2, 3]
letters = ["A", "B", "C"]
for pair in zip(numbers, letters):
	print(pair)

for n, l in zip(numbers, letters):
	print(n,l)
    
    
    
#(1, 'A')
#(2, 'B')
#(3, 'C')
#1 A
#2 B
#3 C

unzip

zip() 함수로 엮어 놓은 데이터를 다시 해체(unzip)하고 싶을 때도 zip() 함수를 사용할 수 있습니다.
먼저 zip() 함수로 2개의 터플의 데이터를 엮은 후 리스트로 변환해보겠습니다.

numbers = (1, 2, 3)
letters = ("A", "B", "C")
pairs = list(zip(numbers, letters))
print(pairs)
#[(1, 'A'), (2, 'B'), (3, 'C')]


numbers, letters = zip(*pairs)

print(numbers)
#(1, 2, 3)

print(letters)
#('A', 'B', 'C')

dictionary

keys = [1, 2, 3]
values = ["A", "B", "C"]
dict(zip(keys, values))
#{1: 'A', 2: 'B', 3: 'C'}

오늘 푼 문제

https://programmers.co.kr/learn/courses/30/lessons/43165

https://programmers.co.kr/learn/courses/30/lessons/49994

https://leetcode.com/problems/insertion-sort-list

https://leetcode.com/problems/largest-number

https://www.acmicpc.net/problem/5052

회고

버블정렬, 삽입정렬, 선택정렬을 배웠는데 직접 구현하는거 자체가 어렵지는 않았다.
그리고 코딩테스트할 때는 sort() 내장함수를 사용하게 될 거고 zip() 이라는 것도 사용하게 된다.
문제를 풀다보면 저런 함수를 몰라서 찾아보고 적용하고 푸는 경우가 많아서 저런 함수가 있다는걸 알아두면 좋을것 같아서 정리해봤다.

항해톡을 진행했는데 주제는 '동기와 비동기', 'DB 인덱스' 라는 주제였다.
발표를 맡아서 진행한다는것 자체가 알고리즘을 공부하면서 저러한 주제에 대해서도 충분히 공부하고 발표자료를 준비해야 한다는 것을 느꼈다.

물론 듣기만 했지만, 나도 혼자서 정리해 두어야 할 주제이라고 생각하고, 시간내서 정리해 봐야겠다.

풀었던 문제들은 엄청 어렵지는 않았지만 그렇게 쉬운문제도 아니라고 생각이 들었다. 힌트를 본 문제도 있었고 타임아웃나서 다시 처음부터 접근해서 푼 문제도 있었다. 결론은 복습이 답인 것 같다.