[Algorithm]

🦕 bubbleSort

🍀 문제 풀이

🌲 회고

묻고싶습니다. 왜 실행초과가 계속나는지..정석처럼 풀었는데 실행초과만 30분째... 결국 교수님 찾아뵙고 힌트를 얻어 해결... 아침부터 너무나 버블sort 혼이 나가버린 상태..알고리즘 점점 어렵다는 생각이..교수님도 이해할 수 없다고..실행초과가 왜 나는지 여부가 이상하다고 하시는데 만드신 담당자한테 묻고싶어지네요..

⭐️ 정리하기

• 단순히 인접한 두 원소를 확인하여, 정렬이 안되어 있다면 위치를 서로 변경한다.
• 서로 인접한 두 원소를 비교하는 형태가 거품과 같다고 하여 붙여진 이름이다.
• 시간 복잡도 O(N^2)로 비효율적인 정렬 알고리즘 중 하나다.

🛠️동작방식

• 각 단계에서는 인접한 두 개의 원소를 비교하여 필요시 위치를 변경한다.
• 첫째와 둘째를 비교, 둘째와 셋째를 비교, 셋째와 넷째를 비교하는 방식이다.
• 한 번의 단계가 수행되면, 가장 큰 원소가 맨 뒤로 이동한다.
• 따라서, 그 다음 단계에서는 맨 뒤로 이동한 데이터는 정렬에서 제왼한다.
  [핵심] 각 단계를 거칠 때마다 가장 큰 값을 하나씩 확실하게 결정하는 것으로 이해할 수 있다.

🧱 Bubble Sort의 시간 복잡도

• 최악의 경우 시간 복잡도 O(N^2)을 보장한다.
• 이미 정렬된 배열에 대해서 모든 비교가 필요하므로, 굉장히 비효율적인 정렬 알고리즘 중 하나에 속한다.