거품정렬 구현

1 개요

거품정렬 구현 bubble_sort()

• 기본형과 개선형이 있음
• 기본형 정도만 알아두면 될 듯
• swapped 플래그를 적용하면 평균적인 속도 향상이 약간 있겠으나 대세에는 큰 변화가 없음

성능이 중요하다면 다른 알고리즘 사용을 권장함

2 C

C언어 거품정렬 구현 문서를 참고하십시오.

기본형

#include <stdio.h>
void bubble_sort(int a[], int size) {
    int i, j, temp;
    for(i=0; i<size-1; i++) {
		for(j=0; j<size-i-1; j++) {
			if(a[j] > a[j+1]) {
				temp=a[j]; a[j]=a[j+1]; a[j+1]=temp;
			}
		}
	}
}
int main() {
	int arr[] = {9,1,22,4,0,-1,1,22,100,10};
	int size = sizeof(arr)/sizeof(int);
	bubble_sort(arr, size);
	for(int i=0; i<size; i++) printf("%d ", arr[i]);
	// -1 0 1 1 4 9 10 22 22 100 
}

개선형 (swapped 플래그 적용)

#include <stdio.h>
void bubble_sort(int a[], int size) {
    int i, j, temp, swapped;
    for(i=0; i<size-1; i++) {
        swapped = 0;
		for(j=0; j<size-i-1; j++) {
			if(a[j] > a[j+1]) {
				temp = a[j]; a[j] = a[j+1]; a[j+1] = temp;
				swapped = 1;
			}
		}
		if( swapped == 0 ) break;
	}
}
int main() {
	int arr[] = {9,1,22,4,0,-1,1,22,100,10};
	int size = sizeof(arr)/sizeof(int);
	bubble_sort(arr, size);
	for(int i=0; i<size; i++) printf("%d ", arr[i]);
	// -1 0 1 1 4 9 10 22 22 100 
}

3 C++

C++ 거품정렬 구현 문서를 참고하십시오.

기본형

#include <iostream>
void bubble_sort(int a[], int size) {
    int i, j;
    for(i=0; i<size-1; i++) {
    	for(j=0; j<size-i-1; j++) {
    		if(a[j] > a[j+1]) std::swap(a[j], a[j+1]);
    	}
    }
}
int main() {
    int arr[] = {9,1,22,4,0,-1,1,22,100,10};
    int size = sizeof(arr)/sizeof(int);
    bubble_sort(arr, size);
    for(int i=0; i<size; i++) std::cout << arr[i] << " ";
    // -1 0 1 1 4 9 10 22 22 100 
}

개선형 (swapped 플래그 적용)

#include <iostream>
void bubble_sort(int a[], int size) {
    int i, j;
    bool swapped;
    for(i=0; i<size-1; i++) {
        swapped = false;
    	for(j=0; j<size-i-1; j++) {
    		if(a[j] > a[j+1]) {
    			std::swap(a[j], a[j+1]);
    			swapped = true;
    		}
    	}
    	if( !swapped ) break;
    }
}
int main() {
    int arr[] = {9,1,22,4,0,-1,1,22,100,10};
    int size = sizeof(arr)/sizeof(int);
    bubble_sort(arr, size);
    for(int x: arr) std::cout << x << " ";
    // -1 0 1 1 4 9 10 22 22 100 
}

4 C#

C샵 거품정렬 구현 문서를 참고하십시오.

using System;
class Program {
    static void bubbleSort(int[] a) {
        int i, j, temp, size=a.Length;
        for(i=0; i<size-1; i++) {
            for(j=1; j<size-i; j++) {
                if (a[j-1] > a[j]) {
                    temp=a[j-1]; a[j-1]=a[j]; a[j]=temp;
                }
            }
        }
    }
    static void Main() {
        int[] arr = {9,1,22,4,0,-1,1,22,100,10};
        bubbleSort(arr);
        Console.Write(string.Join(",",arr));
        // -1,0,1,1,4,9,10,22,22,100
    }
}

5 Java

Java 거품정렬 구현 문서를 참고하십시오.

기본형

public class MyClass {
    static void bubble_sort(int[] a) {
    	int i, j, temp, size=a.length;
    	for(i=0; i<size-1; i++) {
    		for(j=1; j<size-i; j++) {
    			if(a[j-1] > a[j]) {
    				temp=a[j-1]; a[j-1]=a[j]; a[j]=temp;
    			}
    		}
    	}
    }
    public static void main(String args[]) {
    	int[] arr = {9,1,22,4,0,-1,1,22,100,10};
    	bubble_sort(arr);
    	for(int x: arr) System.out.format( "%d ", x );
    	// -1 0 1 1 4 9 10 22 22 100 
    }
}

개선형 (swapped 플래그 적용)

public class MyClass {
    static void bubble_sort(int[] a) {
    	int i, j, temp, size=a.length;
    	boolean swapped;
    	for(i=0; i<size-1; i++) {
    	    swapped = false;
    		for(j=1; j<size-i; j++) {
    			if(a[j-1] > a[j]) {
    				temp=a[j-1]; a[j-1]=a[j]; a[j]=temp;
    				swapped = true;
    			}
    		}
    		if( !swapped ) break;
    	}
    }
    public static void main(String args[]) {
    	int[] arr = {9,1,22,4,0,-1,1,22,100,10};
    	bubble_sort(arr);
    	for(int x: arr) System.out.format( "%d ", x );
    	// -1 0 1 1 4 9 10 22 22 100 
    }
}

6 Perl

Perl 거품정렬 구현 문서를 참고하십시오.

sub bubble_sort {
    my $a=shift;
    $size=@$a;
    for $i (0..$size-2) {
        for $j (1..$size-$i-1) {
            (@$a[$j-1],@$a[$j]) = (@$a[$j],@$a[$j-1]) if @$a[$j-1]>@$a[$j];
        }
    }
}
@arr = (9,1,22,4,0,-1,1,22,100,10);
bubble_sort(\@arr);
print join(',',@arr);
# -1,0,1,1,4,9,10,22,22,100

7 PHP

PHP 거품정렬 구현 문서를 참고하십시오.

기본형

<?php
function bubble_sort(&$a) {
	$size = count($a);
	for($i=0; $i<$size-1; $i++) {
		for($j=1; $j<$size-$i; $j++) {
			if($a[$j-1] > $a[$j]) {
				$temp=$a[$j-1]; $a[$j-1]=$a[$j]; $a[$j]=$temp;
			}
		}
	}
}
$arr = [9,1,22,4,0,-1,1,22,100,10];
bubble_sort( $arr );
echo implode(',', $arr);
# -1,0,1,1,4,9,10,22,22,100

개선형 (swapped 플래그 적용)

<?php
function bubble_sort(&$a) {
	$size = count($a);
	for($i=0; $i<$size-1; $i++) {
		$swapped = false;
		for($j=1; $j<$size-$i; $j++) {
			if($a[$j-1] > $a[$j]) {
				$temp=$a[$j-1]; $a[$j-1]=$a[$j]; $a[$j]=$temp;
				$swapped = true;
			}
		}
		if( !$swapped ) break;
	}
}
$arr = [9,1,22,4,0,-1,1,22,100,10];
bubble_sort( $arr );
echo implode(',', $arr);
# -1,0,1,1,4,9,10,22,22,100

8 Python

Python 거품정렬 구현 문서를 참고하십시오.

def bubble_sort(a):
	size = len(a)
	for i in range(size-1):
		for j in range(size-i-1):
			if a[j]>a[j+1]: a[j],a[j+1] = a[j+1],a[j]
arr = [9,1,22,4,0,-1,1,22,100,10]
bubble_sort(arr)
print( arr )
# [-1, 0, 1, 1, 4, 9, 10, 22, 22, 100]

9 Ruby

Ruby 거품정렬 구현 문서를 참고하십시오.

def bubble_sort(a)
    for i in (0...a.size-1)
        for j in (0...a.size-i-1)
            a[j],a[j+1] = a[j+1],a[j] if a[j]>a[j+1]
        end
    end    
end
arr = [9,1,22,4,0,-1,1,22,100,10]
bubble_sort(arr)
print arr
# [-1, 0, 1, 1, 4, 9, 10, 22, 22, 100]

10 Scala

object MyClass {
	def bubble_sort(arr: Array[Int]) =  {
		var temp, size = arr.length
		for(i<-0 until size; j<-1 until size-i) {
			if(arr(j-1) > arr(j)) {
				temp = arr(j-1)
				arr(j-1) = arr(j)
				arr(j) = temp
			}
		}
	}
	def main(args: Array[String]) {
	    var arr = Array(3,4,2,1,7,5,8,9,0,6,100,10)
	    bubble_sort( arr )
	    print( arr.mkString(" ") )
	    // 0 1 2 3 4 5 6 7 8 9 10 100
	}
}

11 같이 보기

• 거품정렬
• 정렬 구현
• 삽입정렬 구현

12 참고

• https://www.interviewbit.com/tutorial/bubble-sort/
• https://www.geeksforgeeks.org/bubble-sort/