버블 정렬

버블 정렬 : 현재 위치의 원소와 현재 위치의 왼쪽에 위치한 원소의 크기를 비교하며 정렬해나간다.

 

bubble_sort(A[], n)

{

    for last ← n donwto 2

        for i ← 1 to last-1

            if(A[i]>A[i+1])then A[i] ↔ A[i+1];

}

 

알고리즘 실행을 위한 랜덤 배열 생성

import random

sample_list= random.sample(range(1000),100)
print(sample_list)

배열에서 가장 큰 원소를 찾는 함수

def largest(list, last):
  r=0
  for i in range(1, last):
    if list[i] > list[r]:
      r = i
      
  return r

버블 정렬 함수

def bubble_sort_book(list):
  for j in range(len(list)-1, 0, -1):
    sorted = True
    for i in range(j):
      if list[i]>list[i+1]:
        list[i], list[i+1] = list[i+1], list[i]
        sorted = False
    if sorted:
      print("is sorted")
      break

 주어진 배열 list의 마지막 원소부터 시작한다. 첫 번째 원소부터 정렬을 시작해나가며 j번째 원소까지 정렬한다.

 sorted의 역할은 정렬을 해나가다가 이미 정렬이 되어있는 부분을 만나면 순환이 중단될 수 있도록 해준다.

 

 

재귀 호출을 사용한 버블 정렬 함수

def bubble_sort_re(list, flag = 0):
  if flag == len(list) - 1:
    return

  for i in range(1, len(list) - flag):
    if list[i]<list[i-1]:
      list[i], list[i-1] = list[i-1], list[i]
  flag+=1
  bubble_sort_re(list, flag)

 flag를 기준으로 재귀 호출의 중단점을 정한다. 정렬되지 않은 배열의 길이만큼 반복문을 돌면서 버블 정렬을 수행해준다.

 

 

 대충 본다면 재귀 호출을 사용하나 사용하지 않나 크게 변하는 내용은 없는 거 같다. 내가 작성한 내용으로는 그게 그거인 것 같은 느낌이 든다.