알고리즘 / 기술면접 스터디 공부 - 알고리즘 이론(기본정렬 알고리즘)

 

1. 알고리즘 연습 방법

• 연습장과 펜을 준비하자.
• 알고리즘 문제를 읽고 분석한 후에,
• 간단하게 테스트용으로 매우 간단한 경우부터 복잡한 경우 순서대로 생각해보면서, 연습장과 펜을 이용하여 알고리즘을 생각해본다.
• 가능한 알고리즘이 보인다면, 구현할 알고리즘을 세부 항목으로 나누고, 문장으로 세부 항목을 나누어서 적어본다.
• 코드화하기 위해, 데이터 구조 또는 사용할 변수를 정리하고,
• 각 문장을 코드 레벨로 적는다.
• 데이터 구조 또는 사용할 변수가 코드에 따라 어떻게 변하는지를 손으로 적으면서, 임의 데이터로 코드가 정상 동작하는지를 연습장과 펜으로 검증한다.

 

 

2. 버블 정렬

(1) 버블 정렬이란?

: 앞에서부터 2개씩 비교해서, 정렬을 시킴

 

버블정렬 이해 참고자료 : https://visualgo.net/en/sorting?slide=1 

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

 

ex) 버블 정렬의 방식으로 "52" 정렬하기

1TRUN : 25 

 

ex) 버블 정렬의 방식으로 " 542" 정렬하기

1TRUN : 452 - 425

2TRUN : 245 - 245

 

ex) 버블 정렬의 방식으로 "5231" 정렬하기

1TRUN : 2531 - 2351 - 2315

2TRUN : 2315 - 2135 - 2135

3TRUN : 1235 - 1235 - 1235

 

 

이러한 로직을 정리하면,

데이터 길이	조건 체크	턴
2	1	1
3	2	2
4	3	3

+ 패턴 : 1턴을 돌 때마다, 제일 마지막에는 가장 높은 값이 위치됨

 

(2) 데이터가 2개 있을 때, 버블 정렬 구현

 

위의 로직에 의해서, 다음과 같이 코드를 작성할 수 있음

for index in range (데이터길이 - 1) :

    for index2 in range(데이터길이 - index - 1) :

        if 앞데이터 > 뒤데이터 :

                swap(앞데이터, 뒤데이터)

 

 

(3) 알고리즘 구현

1. for num in range(len(data_list)) 반복
2. swap = 0 (교환이 되었는지를 확인하는 변수를 두자)
3. 반복문 안에서, for index in range(len(data_list) - num - 1) n - 1번 반복해야 하므로
4. 반복문안의 반복문 안에서, if data_list[index] > data_list[index + 1] 이면
5. data_list[index], data_list[index + 1] = data_list[index + 1], data_list[index]
6. swap += 1
7. 반복문 안에서, if swap == 0 이면, break 끝

 

(4) 버블 정렬 코드 구현

def bubblesort(data):
    for index in range(len(data) - 1):
        swap = False
        for index2 in range(len(data) - index - 1):
            if data[index2] > data[index2 + 1]:
                data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
                swap = True
        
        if swap == False:
            break
    return data

 

 

3. 삽입정렬

: 크기 비교 후, 데이터를 특정 위치에 삽입함 

 

삽입정렬 참고자료 : https://visualgo.net/en/sorting?slide=1 

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

 

ex) 버블 정렬의 방식으로 "53" 정렬하기

53 - 35

 

ex) 버블 정렬의 방식으로 "532" 정렬하기

352 - 235

 

ex) 버블 정렬의 방식으로 "5324" 정렬하기

3524 - 2354 - 2345

 

이러한 로직을 정리하면,

데이터 길이	조건 체크	턴
2	1	1
3	2	2
4	3	3

 

(2) 데이터가 2개 있을 때, 삽입정렬 구현

 

위의 로직에 의해서, 다음과 같이 코드를 작성할 수 있음

for index in range (데이터길이 - 1) :

    for index2 in range(index + 1, 1, -1) :

        if data[index2] < data[index2-1] :

                swap(data[index2], data[index2-1])

       else : break

 

 

(3) 알고리즘 구현

1. for stand in range(len(data_list)) 로 반복
2. key = data_list[stand]
3. for num in range(stand, 0, -1) 반복
   • 내부 반복문 안에서 data_list[stand] < data_list[num - 1] 이면,
     • data_list[num - 1], data_list[num] = data_list[num], data_list[num - 1]

 

 (4) 삽입 정렬 코드 구현

def insertion_sort(data):
    for index in range(len(data) - 1):
        for index2 in range(index + 1, 0, -1):
            if data[index2] < data[index2 - 1]:
                data[index2], data[index2 - 1] = data[index2 - 1], data[index2]
            else:
                break
    return data

 

4. 선택정렬

(1) 선택정렬이란 ?

: 주어진 데이터 중, 최소값을 찾음 -> 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함 -> 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함

 

선택정렬 참고자료 : https://visualgo.net/en/sorting?slide=1 

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

ex) 버블 정렬의 방식으로 "5431" 정렬하기

1435 - 1345 - 1345

 

 

 

(2) 데이터가 2개 있을 때, 선택정렬 구현

for stand in range(len(data) - 1) :

    lowest = stand

    for index in range(stand + 1, 데이터 길이) :

         if  data[lowst] > data[index] :

               lowst = index

    swap (lowst, stand)

 

 

(3) 알고리즘 구현

1. for stand in range(len(data_list) - 1) 로 반복
2. lowest = stand 로 놓고,
3. for num in range(stand, len(data_list)) stand 이후부터 반복
   • 내부 반복문 안에서 data_list[lowest] > data_list[num] 이면,
     • lowest = num
4. data_list[num], data_list[lowest] = data_list[lowest], data_list[num]

 

(4) 선택 정렬 코드 구현

def selection_sort(data):
    for stand in range(len(data) - 1):
        lowest = stand
        for index in range(stand + 1, len(data)):
            if data[lowest] > data[index]:
                lowest = index
        data[lowest], data[stand] = data[stand], data[lowest]
    return data