201215 개발일지(8일차) - 파이썬 정렬 알고리즘(버블 정렬) + 맥북 데이터복구 포기 및 포맷완료

버블정렬 오름차순 알고리즘

아래 그림처럼 이웃한 원소를 비교하고, 필요하면 교환하는 정렬 작업
(일련의 비교&교환하는 과정을 패스라고 한다.)
위의 그림을 보면 맨 오른쪽에 위치한 원소들부터 비교해서 내려오는 것을 주목해야 한다.

<버블정렬 오름차순 관련 코드>

x=[3,5,4,8,22,6,2]

n=len(x)

for i in range(n-1):           		#왼쪽에는 오름차순으로 차근차근 정렬이 되어감
  for j in range(n-1, i, -1):  		#맨 오른쪽부터 비교하는 과정
    if x[j] < x[j-1]:
      x[j], x[j-1] = x[j-1], x[j]

print(x)

+ 알고리즘 개선 1 : 안쪽 for문에 패스 횟수를 세어 함수를 종료해도 되는지 판단하자

passes에 해당하는 변수로 종료여부 확인

x=[3,5,4,8,22,6,2]

n=len(x)

for i in range(n-1):           		#왼쪽에는 오름차순으로 차근차근 정렬이 되어감
  passes = 0                   		#pass 횟수 0으로 지정
  for j in range(n-1, i, -1):  		#맨 오른쪽부터 비교하는 과정
    if x[j] < x[j-1] :
      x[j], x[j-1] = x[j-1], x[j]
      passes = passes +1       		#pass가 일어나면 pass에 1을 더함
    if passes == 0:
      break
    
print(x)

+ 알고리즘 개선 2 : 마지막으로 패스가 일어난 지점을 활용(변수 last)하여 개선

x=[3,5,4,8,22,6,2]

n=len(x)
k=0

while k < n-1:
  last= n-1
  for j in range(n-1, k, -1):  
    if x[j] < x[j-1] :
      x[j], x[j-1] = x[j-1], x[j]
      last=j

  k= last
    
print(x)

+결국 맥북은.. 내장하드 데이터 살리기 포기하고, 포맷해서 다시 셋팅했다.
처음같은 마음으로 시작해야겠다 ㅋㅋㅋㅋ 파이팅! 할 수 있다