버블정렬

버블정렬은 인접한 두 데이터의 크기를 비교해 정렬하는 방식

구현은 쉬운편이나 O(n2) 시간 복잡도를 갖는다.

 

해당 알고리즘은 위처럼 인덱스를 넘겨가며 데이터의 크기를 비교한 뒤

원하는 조건으로 정렬해주면 된다.

 

이때 전체 배열의 한 루프가 종료되면 가장 마지막 데이터는 정렬이 완료된다는것을 알수있다.

한번의 루프가 종료될때마다 탐색구간이 줄어들며 비교대상이 없을때까지 반복해주면 된다.

 

또한 한번의 루프동안 교체가 일어나지 않는다면 정렬이 완료된것으로 간주하면 된다.

 

문제

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

 

풀이

Sort(int.Parse(Console.ReadLine()));

void Sort(int count)
{
    int[] arr = new int[count];
    bool isChanged;

    for (int i = 0; i < count; i++)
    {
        arr[i] = int.Parse(Console.ReadLine());
    }

    int lastPoint = 0;

    while (true)
    {
        isChanged = false;

        for (int i = 1; i < count - lastPoint; i++)
        {
            if(arr[i] < arr[i-1])
            {
                int temp = arr[i];
                arr[i] = arr[i-1];
                arr[i-1] = temp;

                if(!isChanged)
                    isChanged = true;
            }
        }

        if(!isChanged)
            break;

        lastPoint++;
    }

    for (int i = 0; i < arr.Length; i++)
    {
        System.Console.WriteLine(arr[i]);
    }
}

 

미흡한부분이나 개선될 수 있는부분이 있다면 댓글 부탁드립니다.