1. 알고리즘 정렬, 버블정렬, 선택정렬

sorting

대표적인 정렬1 : 버블정렬(bubble sort)

0. 알고리즘 연습 방법

• 알고리즘을 잘 작성하기 위해서는 잘 작성된 알고리즘을 이해하고, 스스로 만들어봐야 함
  • 모사! 그림을 잘 그리기 위해서는 잘그린 그림을 모방하는 것부터 시작한다

알고리즘 연습방법

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

기술면접도 연습장을주고나 보드에 적어서 알고리즘을 설명해야 된다.

1. 정렬(sorting)이란?

• 정렬(sorting)이란 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것이다.
• 정렬은 프로그램 작성시 빈번하게 필요로 한다.
• 다양한 알고리즘이 고안되었으며, 알고리즘 학습의 필수이다.

2. 버블정렬 (bubble sorting)이란?

• 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘

3. 어떻게 코드로 만들까?

손으로 코딩 해보기

먼저 손으로 로직이 어떤 방식으로 돌아가야 하는지 손으로 적어본다.

• 로직 한번에 로직-(n)이 몇번씩 돌아가야 되는 경우면 반복문(for문)을 이용해서 풀 수 있음을 깨닫는다.
• 로직의 반복 횟수는 데이터개수나 index를 활용하여 정리한다.

손코딩을 코딩프로그램에 옮긴다.

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

import random
data_list=random.sample(range(100),50)
bubblesort(data_list)

결과는 다음과 같다.

[2,
 3,
 4,
 5,
 10,
 13,
 14,
 15,
 18,
 19,
 20,
 22,
 25,
 26,
 28,
 29,
 33,
 34,
 35,
 36,
 38,
 46,
 49,
 50,
 51,
 53,
 54,
 55,
 56,
 57,
 60,
 64,
 65,
 66,
 73,
 78,
 79,
 80,
 81,
 82,
 84,
 85,
 86,
 92,
 93,
 94,
 96,
 97,
 98,
 99]

시간복잡도

• 반목문이 두개 : O(n^2)
• 완전정렬이 되어있을 때 최선은 O(n)

대표적인 정렬2 : 선택정렬(selection sorting)

1. 주어진 데이터 중 최소값을 찾는다.
2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체 한다.
3. 반복 : 나머지 데이터에서 최솟값을 찾아 맨 앞 다음에 위치한 값과 교체하고, 동일한 방법으로 반복한다.

손코딩은 버블정렬과 비슷하게 한다.

def selectionsort(data) : 
    for index in range(len(data)-1) : 
        lowest=index
        for i in range(index+1,len(data)) : 
            if data[i] <data[lowest] : 
                lowest=i
        data[index],data[lowest]=data[lowest],data[index]
    return data

import random
data_list=random.sample(range(100),50)
selectionsort(data_list)

결과는 다음과 같다.

[2,
 3,
 4,
 5,
 6,
 8,
 9,
 11,
 12,
 14,
 15,
 16,
 19,
 21,
 22,
 24,
 25,
 34,
 35,
 38,
 42,
 43,
 44,
 49,
 50,
 51,
 55,
 56,
 57,
 59,
 60,
 61,
 64,
 66,
 67,
 68,
 72,
 74,
 78,
 79,
 81,
 82,
 84,
 85,
 86,
 93,
 95,
 97,
 98,
 99]

시간복잡도

• 반목문이 두개 : O(n^2)