이번에 다룰 내용은 여러 정렬 알고리즘 중 하나인 버블정렬이다.
바로 버블정렬의 개념부터 알아보자.
버블정렬이란?
인접한 값을 순차적으로 계속 비교하여 위치를 바꾸면서 최대, 최소값을 구해가는 정렬 방식이다. 다시 말해, A>B or A<B의 조건식을 이용하여 1회전 할 때마다 큰 값이든 작은 값이든 하나씩 위치를 맞춰가는 정렬인 것이다.
따라서 시간 복잡도는 O(n^2)가 된다.
여기서 오름차순으로 정렬을 하고싶다 하면 A>B, 내림차순으로 정렬을 하고싶다 하면 A<B로 조건식을 맞춰주면 된다.
아래의 이미지를 한번 봐보자.
위의 이미지에 쓰여져있는 설명을 한번 읽어보면 어느 형식으로 진행되는지 알 수 있을 것이다.
이제 이 버블정렬의 장 단점을 알아보자.
장점
- 소스 구현이 간단한 편이다.
단점
- 구조상 모든 요소들을 비교하고 이동시키기 때문에 시간에 있어서 효율적이지 못하다.
정렬 알고리즘 테스트 결과
이제 버블 정렬 구현 소스로 한번 봐보자.
(C# Source)
using System;
namespace Jeongkyun_BubbleSort
{
public class Program
{
public static void Main(string[] args)
{
int[] nArr = new int[] { 1, 7, 5, 34, 5, 2, 23, 54, 1 };
nArr = arr_swap_bubble_sort(nArr);
Print(nArr);
Console.ReadKey();
}
/// <summary>
/// 버블 정렬 + SWAP 함수
/// </summary>
/// <param name="arr">배열 변수</param>
static int[] arr_swap_bubble_sort(int[] arr)
{
int temp = -1;
//인덱스 1번부터 검사
for (int i = 1; i < arr.Length; i++)
{
// i+1 ~ arr.Length의 길이까지 검사
for (int j = i+1; j < arr.Length; j++)
{
//arr[j]보다 비교대상이 크면 Swap 진행
if (arr[i] > arr[j])
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
/// <summary>
/// Print 함수
/// </summary>
/// <param name="arr_val"></param>
static void Print(int[] arr_val)
{
for (int i = 0; i < arr_val.Length; i++)
{
Console.Write(arr_val[i].ToString() + "\t");
}
}
}
}
반응형
'Algorithm > Concept' 카테고리의 다른 글
[Java] 고급 정렬 - 병합 정렬이란? (개념/ 예제/ 총 정리) (3) | 2022.07.12 |
---|---|
[Java] 동적 계획법과 분할 정복이란? (개념/ 공통점/ 차이점/ 예제) (0) | 2022.07.12 |
[Java] 재귀 용법(recursive call)의 개념과 사용 방식 (예제 / 문제 풀이) (0) | 2022.07.11 |
[Algorithm] 선택 정렬(Selection Sort)에 대해 알아보자! (0) | 2021.12.29 |
[Algorithm] 삽입 정렬(Insertion Sort)에 대해 알아보자! (0) | 2021.12.29 |
댓글