수색…


매개 변수

매개 변수 기술
안정된
자리에
최상의 사례 복잡성 에)
평균 사례 복잡성 O (n ^ 2)
최악의 경우의 복잡성 O (n ^ 2)
공간 복잡성 O (1)

버블 정렬

BubbleSort 는 정렬되지 않은 목록의 각 연속적인 요소 쌍을 비교하고 순서가 맞지 않은 경우 요소를 반전합니다.

다음 예제는 {6,5,3,1,8,7,2,4} 목록의 거품 정렬을 보여줍니다 (각 단계에서 비교 된 쌍은 '**'로 캡슐화됩니다).

{6,5,3,1,8,7,2,4}
{**5,6**,3,1,8,7,2,4} -- 5 < 6 -> swap
{5,**3,6**,1,8,7,2,4} -- 3 < 6 -> swap
{5,3,**1,6**,8,7,2,4} -- 1 < 6 -> swap
{5,3,1,**6,8**,7,2,4} -- 8 > 6 -> no swap
{5,3,1,6,**7,8**,2,4} -- 7 < 8 -> swap
{5,3,1,6,7,**2,8**,4} -- 2 < 8 -> swap
{5,3,1,6,7,2,**4,8**} -- 4 < 8 -> swap

목록을 통한 한 번의 반복 작업 후에 {5,3,1,6,7,2,4,8} 됩니다. 배열의 최대 정렬되지 않은 값 (이 경우 8)은 항상 최종 위치에 도달한다는 점에 유의하십시오. 따라서 목록이 정렬되도록하려면 길이가 n 인 목록에 대해 n-1 번 반복해야합니다.

그래픽:

BubbleSort

자바 스크립트 구현

        function bubbleSort(a)
          {
                var swapped;
                do {
                    swapped = false;
                    for (var i=0; i < a.length-1; i++) {
                        if (a[i] > a[i+1]) {
                            var temp = a[i];
                            a[i] = a[i+1];
                            a[i+1] = temp;
                            swapped = true;
                        }
                    }
                } while (swapped);
            }
    
   var a = [3, 203, 34, 746, 200, 984, 198, 764, 9];
   bubbleSort(a);
   console.log(a); //logs [ 3, 9, 34, 198, 200, 203, 746, 764, 984 ]

C # 구현

버블 정렬은 싱킹 정렬 이라고도합니다. 정렬 할 목록을 반복적으로 탐색하고 인접한 항목의 각 쌍을 비교하며 잘못된 순서로 바뀌면 간단한 정렬 알고리즘입니다.

버블 정렬 예제 버블 정렬 예제

버블 정렬 구현
버블 정렬 알고리즘을 구현하기 위해 C # 언어를 사용했습니다.

public class BubbleSort
{
    public static void SortBubble(int[] input)
    {
        for (var i = input.Length - 1; i >= 0; i--)
        {
            for (var j = input.Length - 1 - 1; j >= 0; j--)
            {
                if (input[j] <= input[j + 1]) continue;
                var temp = input[j + 1];
                input[j + 1] = input[j];
                input[j] = temp;
            }
        }
    }

    public static int[] Main(int[] input)
    {
        SortBubble(input);
        return input;
    }
}

C & C ++ 구현

C++ 에서 BubbleSort 구현 예 :

   void bubbleSort(vector<int>numbers)
   {
       for(int i = numbers.size() - 1; i >= 0; i--) {
           for(int j = 1; j <= i; j++) {
               if(numbers[j-1] > numbers[j]) {
                   swap(numbers[j-1],numbers(j));
               }
           }
       }
   }

C 구현

void bubble_sort(long list[], long n)
{
  long c, d, t;
 
  for (c = 0 ; c < ( n - 1 ); c++)
  {
    for (d = 0 ; d < n - c - 1; d++)
    {
      if (list[d] > list[d+1])
      {
        /* Swapping */
 
        t         = list[d];
        list[d]   = list[d+1];
        list[d+1] = t;
      }
    }
  }
}

버블 정렬 포인터

void pointer_bubble_sort(long * list, long n)
{
  long c, d, t;
 
  for (c = 0 ; c < ( n - 1 ); c++)
  {
    for (d = 0 ; d < n - c - 1; d++)
    {
      if ( * (list + d ) > *(list+d+1))
      {
        /* Swapping */
 
        t         = * (list + d );
        * (list + d )   = * (list + d + 1 );
        * (list + d + 1) = t;
      }
    }
  }
}

Java로 구현

public class MyBubbleSort {
  
    public static void bubble_srt(int array[]) {//main logic
        int n = array.length;
        int k;
        for (int m = n; m >= 0; m--) {
            for (int i = 0; i < n - 1; i++) {
                k = i + 1;
                if (array[i] > array[k]) {
                    swapNumbers(i, k, array);
                }
            }
            printNumbers(array);
        }
    }
  
    private static void swapNumbers(int i, int j, int[] array) {
  
        int temp;
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
  
    private static void printNumbers(int[] input) {
          
        for (int i = 0; i < input.length; i++) {
            System.out.print(input[i] + ", ");
        }
        System.out.println("\n");
    }
  
    public static void main(String[] args) {
        int[] input = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };
        bubble_srt(input);
  
    }
}

파이썬 구현

#!/usr/bin/python

input_list = [10,1,2,11]

for i in range(len(input_list)):
  for j in range(i):
    if int(input_list[j]) > int(input_list[j+1]):
      input_list[j],input_list[j+1] = input_list[j+1],input_list[j]

print input_list


Modified text is an extract of the original Stack Overflow Documentation
아래 라이선스 CC BY-SA 3.0
와 제휴하지 않음 Stack Overflow