목차

• 정렬이란?
• 버블정렬
  • 수도코드
    • 코드 설명
  • 시간 복잡도
  • 평가
  • 구현
    • 파이썬
    • 자바

정렬이란?

• 임의로 나열되어 있는 데이터들을 주어진 항목에 따라 크기 순서대로 작은 순서부터 (오름차순) 또는 큰 순서부터 (내림차순) 늘어놓은 것임
• 정렬되어 있는 데이터들은 다음과 같은 작업을 수행할 때 응용
  ① 데이터를 탐색할 때
  ② 리스트에 있는 다른 항목들을 비교할 때

버블정렬

인접한 2개의 레코드를 비교하여 순서대로 되어 있지 않으면 서로 교환

수도코드

Bubblesort(A) 
   for i from 1 to A.length 
      for j from 0 to A.length - 1
          if A[j] > A[j + 1] 
              swap a[j] with a[j + 1]

코드 설명

• 이 알고리즘은 n번의 라운드로 이뤄져 있음
  • 각 라운드마다 배열의 아이템을 한 번씩 쭉 모두 살펴본다.
    • 연달아 있는 아이템 2개의 순서가 잘못되어 있는 것을 발견하면, 두 아이템을 맞바꾼다.

① 이웃한 두 개의 원소를 비교하여 순서가 서로 다르면 원소의 자리를 서로 바꿈
② 첫번째 원소와 두번째 원소를, 두번째 원소와 세번째 원소를, 이런식으로 (n-1)번째 원소와 마지막 원소와 비교하여 가장 큰 수를 맨 뒤로 이동
③ 다시 처음부터 (n-1) 까지 비교하여 두번째로 큰 수를 위치에 이동
④ 반복 실행

시간 복잡도

배열 전체를쭉 살펴보는 것을 n번

• for문이 2번
  시간 복잡도는 항상 O(\(n^2\))
  

평가

• 이보다 더 비효율적일 수는 없음
• 구현 가능한 가장 느린 정렬 알고리즘

구현

파이썬

def bubblesort(A):
  for i in range(1, len(A)):
    for j in range(0,len(A)-1):
        if A[j] > A[j + 1]:
            A[j], A[j + 1] = A[j + 1], A[j]

자바

public class BubbleSort {
	public static void main(String[] args) {
	int [] A = {3,44,38,5,47,15,36,26};
	int temp = 0;
	for(int i = 1 ; i< A.length; i++ ) {
		for(int j = 0 ; j< A.length-1; j++ ) {
			// 크면 바꾸는 함수입니다
      if(A[j]>A[j+1]) {
				temp = A[j+1];
				A[j+1] = A[j];
				A[j] = temp;
						
			}
		}
	// 정렬된 A를 읽어 출력해주는 함수입니다
  for(int k = 0; k<A.length-1; k++) {
		System.out.println(A[k]);
	}
	}
	}
}

내가 짜본 코드

난 point로 기준을 잡아 while으로 전체를 크게 돌리고
그리고 while문이 실행될 때 마자 각자 돌라가는 코드를 이렇게 표현해 봤다

a = [2,8,4,5,9]
point = 0
while point <= len(a)-1:
    for i in range(point,len(a)-1):
        if a[i] > a[i+1]:
            a[i], a[i+1] = a[i+1], a[i]
    point +=1

[결과값]

print(a)
# [2, 4, 5, 8, 9]

헷 잘 나오는 것 같다