정렬 알고리즘 : 파이썬으로 구현

엑셀에서 버튼 하나로 할 수 있는 데이터 정렬
컴퓨터는 이것을 어떻게 처리하는 것일까?

정렬에는 여러가지 알고리즘들이 있을 수 있지만
파이썬을 통해 가장 기본적인 정렬 알고리즘을 공부해보자.

이 정렬 알고리즘만 봐도 기계를 이해하는데 중요한 밑거름이 될 수 있다.

dog = [0,2,2,6,5,6,3,0,8,2]

위와 같이 전화번호처럼 구성된 dog라는 리스트가 있을 때
어떻게 하면 이것을 순서대로 정렬할 수 있을까?

• 첫째, 가장 작은 수를 골라내야 할 것이고
• 둘째, 가장 작은 수를 제외하고 두번째로 작은 수를 골라내야 할 것이고
• 셋째, 위 알고리즘을 계속 반복해야 할 것이고
• 넷째, 골라낸 작은 수들을 순서대로 새로운 리스트로 만들어내야 할 것이다.

1. 가장 작은 수 골라내기
가장 작은 수를 cat이라고 가정해보자.
dog의 첫번째 수를 cat에 배정하고
dog의 각 수들을 cat과 비교하면서 cat보다 작을때는 그 작은 수를 cat으로 대체시킨다
그렇게 for문이 다 돌고나면 cat은 가장 작은 수가 될 것이다.

for i in dog:         if cat == -1:             cat = i         else:             if i < cat:                 cat = i

2. 골라낸 작은 수를 새로운 정렬 리스트로 만들기

난 fox라는 리스트로 새롭게 정렬된 리스트를 생성할 것이다.

그리고 1번에서 골라진 cat을 제외한 나머지 리스트를 다시 wolf로 저장할 것이다.

(1번 알고리즘으로 두번째, 세번째.... 의 작은 수들을 다시 골라내기 위해서)

우선 for문으로 dog를 다시 탐색하면서

cat과 일치할경우 fox에 적재하고

cat과 일치하지 않을 경우 wolf에 적재한다.

그리고 1번에서 나온 최초의 cat = 0이므로

이것을 초기 실행했을 경우 fox와 wolf는 아래와 같이 될 것이다.

fox = [0, 0]

wolf = [2, 2, 6, 5, 6, 3, 8, 2]

for j in dog:         if j == cat:             fox += [j]         else:             wolf += [j]

3. 반복시키기

자, 이제 위 1번과 2번 과정을 계속해서 반복하면서

두번째, 세번째.. 작은수들을 추가시켜야 한다.

2번에서 나온 wolf를 dog로 만들어주자.

그리고 1, 2번 알고리즘 겉에 len(dog)만큼의 반복을 걸어주자.

그러면 새로운 dog로 다시 1, 2번 알고리즘을 돌릴 수 있게 되고

첫번째 이후의 작은 값들이 fox에 차례대로 들어가게 될 것이다.

최종적으로 리스트를 정렬하는 알고리즘은 아래와 같다.

[전체]

dog = [0,2,2,6,5,6,3,0,8,2] print(dog) n = len(dog) fox = [] for x in range(n):     wolf = []     cat=-1     for i in dog:         if cat == -1:             cat = i         else:             if i < cat:                 cat = i     for j in dog:         if j == cat:             fox += [j]         else:             wolf += [j]     dog = wolf sortResult = fox print(sortResult)

컴퓨터의 사고방식은 결국 +, -, *, /이다.
가감승제를 빛의 속도로 수행하면서 세상의 모든 법칙을 풀어내는것이 컴퓨터이다.
참으로 놀랍다.

엑셀의 정렬 버튼 하나에
위와 같이 논리적인 알고리즘이 숨어 있었던 것이다.