2012-07-06T22:50:30の更新内容

programming/tips/sort_algorithms/index.wiki.txt

current previous
1,933 1,259
 
${smdncms:title,ソートのアルゴリズム}
${smdncms:title,ソートのアルゴリズム}
~
${smdncms:keywords,Java,ソート,並べ替え,アルゴリズム,安定}
${smdncms:keywords,Java,ソート,アルゴリズム}
~
${smdncms:tags,lang/java,lang/c#,lang/vb,algo}
${smdncms:tags,lang/java,algo}
~
${smdncms:document_versions,codelang=cs,codelang=vb,codelang=c,codelang=java}
ソートにはいくつかのアルゴリズムが存在します。 ここではそのアルゴリズムのいくつかをJavaによる実装で紹介していきます。
+

          
+
ソートにはいくつかのアルゴリズムが存在します。 ここではそのアルゴリズムのいくつかをC#等による実装を交えて紹介していきます。
+

          
+
-参考
+
--[[ソート - Wikipedia:http://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%88]]
 

        

        
 
#googleadunit
#googleadunit
 

        

        
~
*アルゴリズムと特徴
*ソートの安定性
~
**ソートの安定性
まずはじめに説明しておくべきことに、ソートの安定性というものがあります。 ソートの安定性とは、同値の場合に並べ替えが起こるか否かのことを言います。 すなわち、同値の場合にソートの前後で並べ替えが起こらないものを''安定性のある''ソートといい、逆に並べ替えが起こるものを''安定性のない''ソートといいます。
+
ソートのアルゴリズムには安定性というものがあります。 ソートの安定性とは、ソートの際に2つの値が同じ場合に並べ替えが起こるか否かのことを言います。
+

          
+
同値の場合にソートの前後で並べ替えが起こらない(ソートの前後で順序が維持される)ものを''安定性のある''ソート、または''安定ソート''といい、逆に並べ替えが起こる(ソートの前後で順序が変わる可能性がある)ものを''安定性のない''ソートといいます。
+

          
+
**内部ソート・外部ソート
+
ソートに際して、データ自体の格納領域を変更することで並べ替えを行うものを''内部ソート''、データ以外の一時領域が必要となるものを''外部ソート''と呼びます。
+

          
+
*ソートのアルゴリズム
+
ソートのアルゴリズムの概要と、各言語の実装例を紹介します。 なお以下で例示する実行結果はソート途中の状態を表すもので、ソートアルゴリズムの処理の量を反映しているわけではありません。
+

          
+
**単純選択法・選択ソート (Selection Sort)
+
単純選択法とは、データの並べ替えられていない部分から最小値を一つ選び出し、最初のデータと交換していくという作業を繰り返すことによりソートを行うものです。 単純選択法は、''安定性のない''ソート、''内部ソート''のアルゴリズムです。
 

        

        
~
#tabpage(C#)
*単純選択法(Selection Sort)
~
#code(cs,単純選択法){{
単純選択法(Selection Sort)とは、データの並べ替えられていない部分から最小値(または最小値)を一つ選び出し、すでに並べ替えられているデータのうち、一番後ろのデータと交換していくという作業を繰り返すことによりソートを行うものです。 単純選択法は、''安定性のない''ソートアルゴリズムです。
+
using System;
 

        

        
-
#code(java){{
 
public class SelectionSort {
public class SelectionSort {
~
  public static void Main()
  public static void main( String[] args ) {
~
  {
    int data[] = { 37, 13, 28, 44, 97, 61, 42, 51, 73, 80 };
~
    int[] data = {8, 3, 5, 4, 9, 2, 6, 0, 7, 1};
    int i, j, k, temp;
 

        

        
 
    // 並べ替える前の並びを表示
    // 並べ替える前の並びを表示
~
    Print(data);
    enumerate( data );
 

        

        
~
    Console.WriteLine("ソート開始");
    System.out.println( "Start..." );
 

        

        
 
    // 単純選択法による並べ替え
    // 単純選択法による並べ替え
~
    for (int i = 0; i < data.Length - 1; i++) {
    for ( i = 0; i < data.length - 1; i++ ) {
~
      // まだ並べ替えられていない部分から最小値を探し出す
      k = i;
~
      int min = i;
      for ( j = i + 1; j < data.length; j++ ) {
~

          
        if ( data[k] > data[j] ) k = j;
+
      for (int j = i + 1; j < data.Length; j++) {
+
        if (data[min] > data[j])
+
          min = j;
 
      }
      }
-
      temp = data[i];
-
      data[i] = data[k];
-
      data[k] = temp;
 

        

        
~
      // 見つかった最小値と最初のデータを入れ替える
      enumerate( data );
+
      int temp = data[i];
+

          
+
      data[i] = data[min];
+
      data[min] = temp;
+

          
+
      Print(data);
 
    }
    }
 

        

        
~
    // 並べ替えた後の並びを表示
    System.out.println( "Finished..." );
+
    Console.WriteLine("ソート終了");
+

          
+
    Print(data);
+
  }
+

          
+
  static void Print(int[] data)
+
  {
+
    Console.WriteLine(string.Join(", ", Array.ConvertAll(data, d => d.ToString())));
+
  }
+
}
+
}}
+
#tabpage(VB)
+
#code(vb,単純選択法){{
+
Imports System
+

          
+
Public Class SelectionSort
+
  Public Shared Sub Main()
+
    Dim data As Integer() = {8, 3, 5, 4, 9, 2, 6, 0, 7, 1}
+

          
+
    ' 並べ替える前の並びを表示
+
    Print(data)
+

          
+
    Console.WriteLine("ソート開始")
+

          
+
    ' 単純選択法による並べ替え
+
    For i As Integer = 0 To data.Length - 2
+
      ' まだ並べ替えられていない部分から最小値を探し出す
+
      Dim min As Integer = i
+

          
+
      For j As Integer = i + 1 To data.Length - 1
+
        If data(min) > data(j) Then min = j
+
      Next
+

          
+
      ' 見つかった最小値と最初のデータを入れ替える
+
      Dim temp As Integer = data(i)
+

          
+
      data(i) = data(min)
+
      data(min) = temp
+

          
+
      Print(data)
+
    Next
+

          
+
    ' 並べ替えた後の並びを表示
+
    Console.WriteLine("ソート終了")
+

          
+
    Print(data)
+
  End Sub
+

          
+
  Shared Sub Print(ByVal data As Integer())
+
    For i As Integer = 0 To data.Length - 1
+
      Console.Write("{0} ", data(i))
+
    Next
+
    Console.WriteLine()
+
  End Sub
+
End Class
+
}}
+
#tabpage(C言語)
+
#code(c,単純選択法){{
+
#include <stdio.h>
+

          
+
#define LENGTH 10
+

          
+
void Print(int data[], int length)
+
{
+
  int i;
+

          
+
  for (i = 0; i < length; i++) {
+
    printf("%d, ", data[i]);
+
  }
+

          
+
  printf("\n");
+
}
+

          
+
void main()
+
{
+
  int data[] = {8, 3, 5, 4, 9, 2, 6, 0, 7, 1};
+

          
+
  // 並べ替える前の並びを表示
+
  Print(data, LENGTH);
+

          
+
  printf("ソート開始\n");
+

          
+
  // 単純選択法による並べ替え
+
  int i, j, min, temp;
+

          
+
  for (i = 0; i < LENGTH - 1; i++) {
+
    // まだ並べ替えられていない部分から最小値を探し出す
+
    min = i;
+

          
+
    for (j = i + 1; j < LENGTH; j++) {
+
      if (data[min] > data[j])
+
        min = j;
+
    }
+

          
+
    // 見つかった最小値と最初のデータを入れ替える
+
    temp = data[i];
+
    data[i] = data[min];
+
    data[min] = temp;
+

          
+
    Print(data, LENGTH);
+
  }
+

          
+
  // 並べ替えた後の並びを表示
+
  printf("ソート終了\n");
+

          
+
  Print(data, LENGTH);
+
}
+
}}
+
#tabpage(Java)
+
#code(java,単純選択法){{
+
public class SelectionSort {
+
  public static void main(String[] args) {
+
    int[] data = {8, 3, 5, 4, 9, 2, 6, 0, 7, 1};
+

          
+
    // 並べ替える前の並びを表示
+
    Print(data);
+

          
+
    System.out.println("ソート開始");
+

          
+
    // 単純選択法による並べ替え
+
    for (int i = 0; i < data.length - 1; i++) {
+
      // まだ並べ替えられていない部分から最小値を探し出す
+
      int min = i;
+

          
+
      for (int j = i + 1; j < data.length; j++) {
+
        if (data[min] > data[j])
+
          min = j;
+
      }
+

          
+
      // 見つかった最小値と最初のデータを入れ替える
+
      int temp = data[i];
+

          
+
      data[i] = data[min];
+
      data[min] = temp;
+

          
+
      Print(data);
+
    }
 

        

        
 
    // 並べ替えた後の並びを表示
    // 並べ替えた後の並びを表示
~
    System.out.println("ソート終了");
    enumerate( data );
+

          
+
    Print(data);
 
  }
  }
 

        

        
~
  static void Print(int[] data) {
  // 配列の要素を列挙する
~
    for (int i = 0; i < data.length; i++) {
  static void enumerate( int[] data ) {
~
      System.out.print(data[i] + ", ");
    for ( int i = 0; i < data.length; i++ ) {
-
      System.out.print( data[i] + ", " );
 
    }
    }
 
    System.out.println();
    System.out.println();
 
  }
  }
 
}
}
 
}}
}}
+
#tabpage-end
 

        

        
 
#prompt(実行結果){{
#prompt(実行結果){{
~
8, 3, 5, 4, 9, 2, 6, 0, 7, 1
37, 13, 28, 44, 97, 61, 42, 51, 73, 80, 
~
ソート開始
Start...
~
0, 3, 5, 4, 9, 2, 6, 8, 7, 1
13, 37, 28, 44, 97, 61, 42, 51, 73, 80, 
~
0, 1, 5, 4, 9, 2, 6, 8, 7, 3
13, 28, 37, 44, 97, 61, 42, 51, 73, 80, 
~
0, 1, 2, 4, 9, 5, 6, 8, 7, 3
13, 28, 37, 44, 97, 61, 42, 51, 73, 80, 
~
0, 1, 2, 3, 9, 5, 6, 8, 7, 4
13, 28, 37, 42, 97, 61, 44, 51, 73, 80, 
~
0, 1, 2, 3, 4, 5, 6, 8, 7, 9
13, 28, 37, 42, 44, 61, 97, 51, 73, 80, 
~
0, 1, 2, 3, 4, 5, 6, 8, 7, 9
13, 28, 37, 42, 44, 51, 97, 61, 73, 80, 
~
0, 1, 2, 3, 4, 5, 6, 8, 7, 9
13, 28, 37, 42, 44, 51, 61, 97, 73, 80, 
~
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
13, 28, 37, 42, 44, 51, 61, 73, 97, 80, 
~
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
13, 28, 37, 42, 44, 51, 61, 73, 80, 97, 
~
ソート終了
Finished...
~
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
13, 28, 37, 42, 44, 51, 61, 73, 80, 97,
 
}}
}}
 

        

        
~
最小値ではなく最大値を探すことで、降順にソートするようになります。
*単純交換法(Bubble Sort)
~

          
単純交換法(Bubble Sort)とは、データの最後尾から順に読んでいき、その一つ前のデータとの大小関係により交換していくという作業を繰り返すことによりソートを行うものです。 決定項(ソートされたデータ)が先頭に向かって泡のように浮き上がる様子から、バブルソートとも呼ばれます。 単純交換法は、''安定性のある''ソートアルゴリズムです。
+
**単純交換法・バブルソート (Bubble Sort)
+
単純交換法とは、データの最後尾から順に読んでいき、その一つ前のデータとの大小関係により交換していくという作業を繰り返すことによりソートを行うものです。 決定項(ソートされたデータ)が先頭に向かって泡のように浮き上がる様子から、バブルソートとも呼ばれます。 単純交換法は、''安定性のある''ソート、''内部ソート''のアルゴリズムです。
+

          
+
#tabpage(C#)
+
#code(cs,単純交換法){{
+
using System;
 

        

        
-
#code(java){{
 
public class BubbleSort {
public class BubbleSort {
~
  public static void Main()
  public static void main( String[] args ) {
~
  {
    int data[] = { 37, 13, 28, 44, 97, 61, 42, 51, 73, 80 };
~
    int[] data = {8, 3, 5, 4, 9, 2, 6, 0, 7, 1};
    int i, j, temp;
 

        

        
 
    // 並べ替える前の並びを表示
    // 並べ替える前の並びを表示
~
    Print(data);
    enumerate( data );
 

        

        
~
    Console.WriteLine("ソート開始");
    System.out.println( "Start..." );
 

        

        
 
    // 単純交換法による並べ替え
    // 単純交換法による並べ替え
~
    for (int i = 0; i < data.Length - 1; i++) {
    for ( i = 0; i < data.length - 1; i++ ) {
~
      // 最後尾からデータを読んでいく
      for ( j = data.length - 1; j > i; j-- ) {
~
      for (int j = data.Length - 1; j > i; j--) {
        if ( data[j - 1] > data[j] ) {
~
        if (data[j - 1] > data[j]) {
          temp = data[j - 1];
+
          // 一つ前のデータの方が大きい場合、位置を交換する
+
          int temp = data[j - 1];
+

          
 
          data[j - 1] = data[j];
          data[j - 1] = data[j];
 
          data[j] = temp;
          data[j] = temp;
~

          
          enumerate( data );
+
          Print(data);
 
        }
        }
 
      }
      }
 
    }
    }
 

        

        
~
    // 並べ替えた後の並びを表示
    System.out.println( "Finished..." );
+
    Console.WriteLine("ソート終了");
+

          
+
    Print(data);
+
  }
+

          
+
  static void Print(int[] data)
+
  {
+
    Console.WriteLine(string.Join(", ", Array.ConvertAll(data, d => d.ToString())));
+
  }
+
}
+
}}
+
#tabpage(VB)
+
#code(vb,単純交換法){{
+
Imports System
+

          
+
Public Class BubbleSort
+
  Public Shared Sub Main()
+
    Dim data As Integer() = {8, 3, 5, 4, 9, 2, 6, 0, 7, 1}
+

          
+
    ' 並べ替える前の並びを表示
+
    Print(data)
+

          
+
    Console.WriteLine("ソート開始")
+

          
+
    ' 単純交換法による並べ替え
+
    For i As Integer = 0 To data.Length - 2
+
      ' 最後尾からデータを読んでいく
+
      For j As Integer = data.Length - 1 To i + 1 Step -1
+
        If data(j - 1) > data(j) Then
+
          ' 一つ前のデータの方が大きい場合、位置を交換する
+
          Dim temp As Integer = data(j - 1)
+

          
+
          data(j - 1) = data(j)
+
          data(j) = temp
+

          
+
          Print(data)
+
        End If
+
      Next
+
    Next
+

          
+
    ' 並べ替えた後の並びを表示
+
    Console.WriteLine("ソート終了")
+

          
+
    Print(data)
+
  End Sub
+

          
+
  Shared Sub Print(ByVal data As Integer())
+
    For i As Integer = 0 To data.Length - 1
+
      Console.Write("{0} ", data(i))
+
    Next
+
    Console.WriteLine()
+
  End Sub
+
End Class
+
}}
+
#tabpage(C言語)
+
#code(c,単純交換法){{
+
#include <stdio.h>
+

          
+
#define LENGTH 10
+

          
+
void Print(int data[], int length)
+
{
+
  int i;
+

          
+
  for (i = 0; i < length; i++) {
+
    printf("%d, ", data[i]);
+
  }
+

          
+
  printf("\n");
+
}
+

          
+
void main()
+
{
+
  int data[] = {8, 3, 5, 4, 9, 2, 6, 0, 7, 1};
+

          
+
  // 並べ替える前の並びを表示
+
  Print(data, LENGTH);
+

          
+
  printf("ソート開始\n");
+

          
+
  // 単純交換法による並べ替え
+
  int i, j, temp;
+

          
+
  for (i = 0; i < LENGTH - 1; i++) {
+
    // 最後尾からデータを読んでいく
+
    for (j = LENGTH - 1; j > i; j--) {
+
      if (data[j - 1] > data[j]) {
+
        // 一つ前のデータの方が大きい場合、位置を交換する
+
        temp = data[j - 1];
+
        data[j - 1] = data[j];
+
        data[j] = temp;
+

          
+
        Print(data, LENGTH);
+
      }
+
    }
+
  }
+

          
+
  // 並べ替えた後の並びを表示
+
  printf("ソート終了\n");
+

          
+
  Print(data, LENGTH);
+
}
+
}}
+
#tabpage(Java)
+
#code(java,単純交換法){{
+
public class BubbleSort {
+
  public static void main(String[] args) {
+
    int[] data = {8, 3, 5, 4, 9, 2, 6, 0, 7, 1};
+

          
+
    // 並べ替える前の並びを表示
+
    Print(data);
+

          
+
    System.out.println("ソート開始");
+

          
+
    // 単純交換法による並べ替え
+
    for (int i = 0; i < data.length - 1; i++) {
+
      // 最後尾からデータを読んでいく
+
      for (int j = data.length - 1; j > i; j--) {
+
        if (data[j - 1] > data[j]) {
+
          // 一つ前のデータの方が大きい場合、位置を交換する
+
          int temp = data[j - 1];
+

          
+
          data[j - 1] = data[j];
+
          data[j] = temp;
+

          
+
          Print(data);
+
        }
+
      }
+
    }
 

        

        
 
    // 並べ替えた後の並びを表示
    // 並べ替えた後の並びを表示
~
    System.out.println("ソート終了");
    enumerate( data );
+

          
+
    Print(data);
 
  }
  }
 

        

        
~
  static void Print(int[] data) {
  // 配列の要素を列挙する
~
    for (int i = 0; i < data.length; i++) {
  static void enumerate( int[] data ) {
~
      System.out.print(data[i] + ", ");
    for ( int i = 0; i < data.length; i++ ) {
-
      System.out.print( data[i] + ", " );
 
    }
    }
 
    System.out.println();
    System.out.println();
 
  }
  }
 
}
}
 
}}
}}
+
#tabpage-end
 

        

        
 
#prompt(実行結果){{
#prompt(実行結果){{
~
8, 3, 5, 4, 9, 2, 6, 0, 7, 1
37, 13, 28, 44, 97, 61, 42, 51, 73, 80, 
~
ソート開始
Start...
~
8, 3, 5, 4, 9, 2, 6, 0, 1, 7
37, 13, 28, 44, 97, 42, 61, 51, 73, 80, 
~
8, 3, 5, 4, 9, 2, 0, 6, 1, 7
37, 13, 28, 44, 42, 97, 61, 51, 73, 80, 
~
8, 3, 5, 4, 9, 0, 2, 6, 1, 7
37, 13, 28, 42, 44, 97, 61, 51, 73, 80, 
~
8, 3, 5, 4, 0, 9, 2, 6, 1, 7
13, 37, 28, 42, 44, 97, 61, 51, 73, 80, 
~
8, 3, 5, 0, 4, 9, 2, 6, 1, 7
13, 37, 28, 42, 44, 97, 51, 61, 73, 80, 
~
8, 3, 0, 5, 4, 9, 2, 6, 1, 7
13, 37, 28, 42, 44, 51, 97, 61, 73, 80, 
~
8, 0, 3, 5, 4, 9, 2, 6, 1, 7
13, 28, 37, 42, 44, 51, 97, 61, 73, 80, 
~
0, 8, 3, 5, 4, 9, 2, 6, 1, 7
13, 28, 37, 42, 44, 51, 61, 97, 73, 80, 
~
0, 8, 3, 5, 4, 9, 2, 1, 6, 7
13, 28, 37, 42, 44, 51, 61, 73, 97, 80, 
~
0, 8, 3, 5, 4, 9, 1, 2, 6, 7
13, 28, 37, 42, 44, 51, 61, 73, 80, 97, 
~
0, 8, 3, 5, 4, 1, 9, 2, 6, 7
Finished...
~
0, 8, 3, 5, 1, 4, 9, 2, 6, 7
13, 28, 37, 42, 44, 51, 61, 73, 80, 97,
+
0, 8, 3, 1, 5, 4, 9, 2, 6, 7
+
0, 8, 1, 3, 5, 4, 9, 2, 6, 7
+
0, 1, 8, 3, 5, 4, 9, 2, 6, 7
+
0, 1, 8, 3, 5, 4, 2, 9, 6, 7
+
0, 1, 8, 3, 5, 2, 4, 9, 6, 7
+
0, 1, 8, 3, 2, 5, 4, 9, 6, 7
+
0, 1, 8, 2, 3, 5, 4, 9, 6, 7
+
0, 1, 2, 8, 3, 5, 4, 9, 6, 7
+
0, 1, 2, 8, 3, 5, 4, 6, 9, 7
+
0, 1, 2, 8, 3, 4, 5, 6, 9, 7
+
0, 1, 2, 3, 8, 4, 5, 6, 9, 7
+
0, 1, 2, 3, 8, 4, 5, 6, 7, 9
+
0, 1, 2, 3, 4, 8, 5, 6, 7, 9
+
0, 1, 2, 3, 4, 5, 8, 6, 7, 9
+
0, 1, 2, 3, 4, 5, 6, 8, 7, 9
+
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
+
ソート終了
+
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
 
}}
}}
 

        

        
 

        

        
~
**単純挿入法・挿入ソート (Insertion Sort)
*単純挿入法(Insertion Sort)
~
単純挿入法とは、ソート済みのデータからソートするデータを入れるべき場所を探し、以降のデータを後ろにずらすことで場所を空けてデータを挿入するという作業を繰り返すことによりソートを行うものです。 単純挿入法は、''安定性のある''ソート、''内部ソート''のアルゴリズムです。
単純挿入法(Insertion Sort)とは、ソート済みのデータからソートするデータを入れるべき場所を探し、場所を空けた後にその部分に挿入するという作業を繰り返すことによりソートを行うものです。 単純挿入法は、''安定性のある''ソートアルゴリズムです。
+

          
+
#tabpage(C#)
+
#code(cs,単純挿入法){{
+
using System;
 

        

        
-
#code(java){{
 
public class InsertionSort {
public class InsertionSort {
~
  public static void Main()
  public static void main( String[] args ) {
~
  {
    int data[] = { 37, 13, 28, 44, 97, 61, 42, 51, 73, 80 };
~
    int[] data = {8, 3, 5, 4, 9, 2, 6, 0, 7, 1};
    int i, j, temp;
 

        

        
 
    // 並べ替える前の並びを表示
    // 並べ替える前の並びを表示
~
    Print(data);
    enumerate( data );
 

        

        
~
    Console.WriteLine("ソート開始");
    System.out.println( "Start..." );
 

        

        
 
    // 単純挿入法による並べ替え
    // 単純挿入法による並べ替え
~
    for (int i = 1; i < data.Length; i++) {
    for ( i = 0; i < data.length; i++ ) {
+
      if (data[i - 1] > data[i]) {
+
        // データが一つ前のデータより小さい場合、以降のデータを後ろにずらしていく
+
        int temp = data[i];
+
        int j;
+

          
+
        for (j = i; j > 0 && data[j - 1] > temp; j--) {
+
          data[j] = data[j - 1];
+
        }
+

          
+
        // ずらした結果空いた部分にデータを入れる
+
        data[j] = temp;
+

          
+
        Print(data);
+
      }
+
    }
+

          
+
    // 並べ替えた後の並びを表示
+
    Console.WriteLine("ソート終了");
+

          
+
    Print(data);
+
  }
+

          
+
  static void Print(int[] data)
+
  {
+
    Console.WriteLine(string.Join(", ", Array.ConvertAll(data, d => d.ToString())));
+
  }
+
}
+
}}
+
#tabpage(VB)
+
#code(vb,単純挿入法){{
+
Imports System
+

          
+
Public Class InsertionSort
+
  Public Shared Sub Main()
+
    Dim data As Integer() = {8, 3, 5, 4, 9, 2, 6, 0, 7, 1}
+

          
+
    ' 並べ替える前の並びを表示
+
    Print(data)
+

          
+
    Console.WriteLine("ソート開始")
+

          
+
    ' 単純挿入法による並べ替え
+
    For i As Integer = 1 To data.Length - 1
+
      If data(i - 1) > data(i) Then
+
        ' データが一つ前のデータより小さい場合、以降のデータを後ろにずらしていく
+
        Dim temp As Integer = data(i)
+
        Dim j As Integer = i
+

          
+
        While j > 0 AndAlso data(j - 1) > temp
+
          data(j) = data(j - 1)
+

          
+
          j -= 1
+
        End While
+

          
+
        ' ずらした結果空いた部分にデータを入れる
+
        data(j) = temp
+

          
+
        Print(data)
+
      End If
+
    Next
+

          
+
    ' 並べ替えた後の並びを表示
+
    Console.WriteLine("ソート終了")
+

          
+
    Print(data)
+
  End Sub
+

          
+
  Shared Sub Print(ByVal data As Integer())
+
    For i As Integer = 0 To data.Length - 1
+
      Console.Write("{0} ", data(i))
+
    Next
+
    Console.WriteLine()
+
  End Sub
+
End Class
+
}}
+
#tabpage(C言語)
+
#code(c,単純挿入法){{
+
#include <stdio.h>
+

          
+
#define LENGTH 10
+

          
+
void Print(int data[], int length)
+
{
+
  int i;
+

          
+
  for (i = 0; i < length; i++) {
+
    printf("%d, ", data[i]);
+
  }
+

          
+
  printf("\n");
+
}
+

          
+
void main()
+
{
+
  int data[] = {8, 3, 5, 4, 9, 2, 6, 0, 7, 1};
+

          
+
  // 並べ替える前の並びを表示
+
  Print(data, LENGTH);
+

          
+
  printf("ソート開始\n");
+

          
+
  // 単純挿入法による並べ替え
+
  int i, j, temp;
+

          
+
  for (i = 1; i < LENGTH; i++) {
+
    if (data[i - 1] > data[i]) {
+
      // データが一つ前のデータより小さい場合、以降のデータを後ろにずらしていく
 
      temp = data[i];
      temp = data[i];
~

          
      for ( j = i - 1; j >= 0 && d < data[j]; j-- ) {
~
      for (j = i; j > 0 && data[j - 1] > temp; j--) {
        data[j + 1] = data[j];
+
        data[j] = data[j - 1];
 
      }
      }
~

          
      data[j + 1] = temp;
~
      // ずらした結果空いた部分にデータを入れる
      enumerate( data );
+
      data[j] = temp;
+

          
+
      Print(data, LENGTH);
 
    }
    }
+
  }
+

          
+
  // 並べ替えた後の並びを表示
+
  printf("ソート終了\n");
 

        

        
~
  Print(data, LENGTH);
    System.out.println( "Finished..." );
+
}
+
}}
+
#tabpage(Java)
+
#code(java,単純挿入法){{
+
public class InsertionSort {
+
  public static void main(String[] args) {
+
    int[] data = {8, 3, 5, 4, 9, 2, 6, 0, 7, 1};
+

          
+
    // 並べ替える前の並びを表示
+
    Print(data);
+

          
+
    System.out.println("ソート開始");
+

          
+
    // 単純挿入法による並べ替え
+
    for (int i = 1; i < data.length; i++) {
+
      if (data[i - 1] > data[i]) {
+
        // データが一つ前のデータより小さい場合、以降のデータを後ろにずらしていく
+
        int temp = data[i];
+
        int j;
+

          
+
        for (j = i; j > 0 && data[j - 1] > temp; j--) {
+
          data[j] = data[j - 1];
+
        }
+

          
+
        // ずらした結果空いた部分にデータを入れる
+
        data[j] = temp;
+

          
+
        Print(data);
+
      }
+
    }
 

        

        
 
    // 並べ替えた後の並びを表示
    // 並べ替えた後の並びを表示
~
    System.out.println("ソート終了");
    enumerate( data );
+

          
+
    Print(data);
 
  }
  }
 

        

        
~
  static void Print(int[] data) {
  // 配列の要素を列挙する
~
    for (int i = 0; i < data.length; i++) {
  static void enumerate( int[] data ) {
~
      System.out.print(data[i] + ", ");
    for ( int i = 0; i < data.length; i++ ) {
-
      System.out.print( data[i] + ", " );
 
    }
    }
 
    System.out.println();
    System.out.println();
 
  }
  }
 
}
}
 
}}
}}
+
#tabpage-end
 

        

        
 
#prompt(実行結果){{
#prompt(実行結果){{
~
8, 3, 5, 4, 9, 2, 6, 0, 7, 1
37, 13, 28, 44, 97, 61, 42, 51, 73, 80, 
~
ソート開始
Start...
~
3, 8, 5, 4, 9, 2, 6, 0, 7, 1
37, 13, 28, 44, 97, 61, 42, 51, 73, 80, 
~
3, 5, 8, 4, 9, 2, 6, 0, 7, 1
13, 37, 28, 44, 97, 61, 42, 51, 73, 80, 
~
3, 4, 5, 8, 9, 2, 6, 0, 7, 1
13, 28, 37, 44, 97, 61, 42, 51, 73, 80, 
~
2, 3, 4, 5, 8, 9, 6, 0, 7, 1
13, 28, 37, 44, 97, 61, 42, 51, 73, 80, 
~
2, 3, 4, 5, 6, 8, 9, 0, 7, 1
13, 28, 37, 44, 97, 61, 42, 51, 73, 80, 
~
0, 2, 3, 4, 5, 6, 8, 9, 7, 1
13, 28, 37, 44, 61, 97, 42, 51, 73, 80, 
~
0, 2, 3, 4, 5, 6, 7, 8, 9, 1
13, 28, 37, 42, 44, 61, 97, 51, 73, 80, 
~
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
13, 28, 37, 42, 44, 51, 61, 97, 73, 80, 
~
ソート終了
13, 28, 37, 42, 44, 51, 61, 73, 97, 80, 
~
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
13, 28, 37, 42, 44, 51, 61, 73, 80, 97, 
~
}}
Finished...
~

          
13, 28, 37, 42, 44, 51, 61, 73, 80, 97,
~
**クイックソート (Quick Sort)
}}
~
クイックソートとは、データから適当な値を選び出し、その値を中心にして大小に分けていくという作業を繰り返すことによりソートを行うものです。 クイックソートは、''安定性のない''ソートアルゴリズムです。

          
-
*クイックソート(Quick Sort)
-
クイックソート(Quick Sort)とは、データから適当な値を選び出し、その値を中心にして大小に分けていくという作業を繰り返すことによりソートを行うものです。 この例では再起によってクイックソートを実装していますが、データ数が多い場合はその分だけ再起的に呼び出されるので注意が必要です。 クイックソートは、''安定性のない''ソートアルゴリズムです。
-
#code(java){{
-
public class QuickSort {
 

        

        
~
この例では再帰によってクイックソートを実装していますが、データ数が多い場合はその分だけ再帰的に呼び出されるので注意が必要です。 再帰を使った実装では再帰のために領域が必要であるとみることもできますが、一般的には''内部ソート''とみなされます。
  static int[] data;
 

        

        
~
#tabpage(C#)
  public static void main( String[] args ) {
~
#code(cs,クイックソート){{
    data = new int[] { 37, 13, 28, 44, 97, 61, 42, 51, 73, 80 };
+
using System;
+

          
+
public class QuickSort {
+
  public static void Main()
+
  {
+
    int[] data = {8, 3, 5, 4, 9, 2, 6, 0, 7, 1};
 

        

        
 
    // 並べ替える前の並びを表示
    // 並べ替える前の並びを表示
~
    Print(data);
    enumerate();
 

        

        
~
    Console.WriteLine("ソート開始");
    System.out.println( "Start..." );
 

        

        
 
    // クイックソートによる並べ替え
    // クイックソートによる並べ替え
~
    QSort(data, 0, data.Length - 1);
    qsort( 0, data.length - 1 );
-

          
-
    System.out.println( "Finished..." );
 

        

        
 
    // 並べ替えた後の並びを表示
    // 並べ替えた後の並びを表示
~
    Console.WriteLine("ソート終了");
    enumerate();
+

          
+
    Print(data);
+
  }
+

          
+
  // クイックソートの実装
+
  static void QSort(int[] data, int left, int right)
+
  {
+
    int j = left; // データの左端を仮の基準点とする
+
    int temp;
+

          
+
    for (int i = left + 1; i <= right; i++) {
+
      if (data[i] < data[left]) {
+
        // 基準点の値よりも小さい値を前方に移動する
+
        j++;
+

          
+
        temp = data[j];
+
        data[j] = data[i];
+
        data[i] = temp;
+
      }
+
    }
+

          
+
    // 仮に置いた基準点の値を新しい基準点に置く
+
    temp = data[left];
+
    data[left] = data[j];
+
    data[j] = temp;
+

          
+
    Print(data);
+

          
+
    // 新しい基準点の位置で範囲を2分割する
+

          
+
    // 基準点の左側に要素がある場合は、さらにその範囲内で並べ替えを行う
+
    if (left < j - 1)
+
      QSort(data, left, j - 1);
+

          
+
    // 基準点の右側に要素がある場合は、さらにその範囲内で並べ替えを行う
+
    if (j + 1 < right)
+
      QSort(data, j + 1, right);
+
  }
+

          
+
  static void Print(int[] data)
+
  {
+
    Console.WriteLine(string.Join(", ", Array.ConvertAll(data, d => d.ToString())));
+
  }
+
}
+
}}
+
#tabpage(VB)
+
#code(vb,クイックソート){{
+
Imports System
+

          
+
Public Class QuickSort
+
  Public Shared Sub Main()
+
    Dim data As Integer() = {8, 3, 5, 4, 9, 2, 6, 0, 7, 1}
+

          
+
    ' 並べ替える前の並びを表示
+
    Print(data)
+

          
+
    Console.WriteLine("ソート開始")
+

          
+
    ' クイックソートによる並べ替え
+
    QSort(data, 0, data.Length - 1)
+

          
+
    ' 並べ替えた後の並びを表示
+
    Console.WriteLine("ソート終了")
+

          
+
    Print(data)
+
  End Sub
+

          
+
  ' クイックソートの実装
+
  Shared Sub QSort(ByVal data As Integer(), ByVal left As Integer, ByVal right As Integer)
+
    Dim j As Integer = left ' データの左端を仮の基準点とする
+
    Dim temp As Integer
+

          
+
    For i As Integer = left To right
+
      If data(i) < data(left) Then
+
        ' 基準点の値よりも小さい値を前方に移動する
+
        j += 1
+

          
+
        temp = data(j)
+
        data(j) = data(i)
+
        data(i) = temp
+
      End If
+
    Next
+

          
+
    ' 仮に置いた基準点の値を新しい基準点に置く
+
    temp = data(left)
+
    data(left) = data(j)
+
    data(j) = temp
+

          
+
    Print(data)
+

          
+
    ' 新しい基準点の位置で範囲を2分割する
+

          
+
    ' 基準点の左側に要素がある場合は、さらにその範囲内で並べ替えを行う
+
    If left < j - 1 Then QSort(data, left, j - 1)
+

          
+
    ' 基準点の右側に要素がある場合は、さらにその範囲内で並べ替えを行う
+
    If j + 1 < right Then QSort(data, j + 1, right)
+
  End Sub
+

          
+
  Shared Sub Print(ByVal data As Integer())
+
    For i As Integer = 0 To data.Length - 1
+
      Console.Write("{0} ", data(i))
+
    Next
+
    Console.WriteLine()
+
  End Sub
+
End Class
+
}}
+
#tabpage(C言語)
+
#code(c,クイックソート){{
+
#include <stdio.h>
+

          
+
#define LENGTH 10
+

          
+
void Print(int data[], int length)
+
{
+
  int i;
+

          
+
  for (i = 0; i < length; i++) {
+
    printf("%d, ", data[i]);
+
  }
+

          
+
  printf("\n");
+
}
+

          
+
// クイックソートの実装
+
void QSort(int data[], int left, int right)
+
{
+
  int i, j, temp;
+

          
+
  j = left; // データの左端を仮の基準点とする
+

          
+
  for (i = left + 1; i <= right; i++) {
+
    if (data[i] < data[left]) {
+
      // 基準点の値よりも小さい値を前方に移動する
+
      j++;
+

          
+
      temp = data[j];
+
      data[j] = data[i];
+
      data[i] = temp;
+
    }
 
  }
  }
 

        

        
~
  // 仮に置いた基準点の値を新しい基準点に置く
  // クイックソートを行う
~
  temp = data[left];
  static void qsort( int left, int right ) {
~
  data[left] = data[j];
    int i, j, temp;
+
  data[j] = temp;
+

          
+
  Print(data, LENGTH);
+

          
+
  // 新しい基準点の位置で範囲を2分割する
+

          
+
  // 基準点の左側に要素がある場合は、さらにその範囲内で並べ替えを行う
+
  if (left < j - 1)
+
    QSort(data, left, j - 1);
+

          
+
  // 基準点の右側に要素がある場合は、さらにその範囲内で並べ替えを行う
+
  if (j + 1 < right)
+
    QSort(data, j + 1, right);
+
}
+

          
+
void main()
+
{
+
  int data[] = {8, 3, 5, 4, 9, 2, 6, 0, 7, 1};
+

          
+
  // 並べ替える前の並びを表示
+
  Print(data, LENGTH);
 

        

        
~
  printf("ソート開始\n");
    if ( left >= right ) return;
 

        

        
~
  // クイックソートによる並べ替え
    j = left;
+
  QSort(data, 0, LENGTH - 1);
 

        

        
~
  // 並べ替えた後の並びを表示
    for ( i = left + 1; i <= right; i++ ) {
~
  printf("ソート終了\n");
      if ( data[i] < data[left] ) {
~

          
        temp = data[++j];
+
  Print(data, LENGTH);
+
}
+
}}
+
#tabpage(Java)
+
#code(java,クイックソート){{
+
public class QuickSort {
+
  public static void main(String[] args) {
+
    int[] data = {8, 3, 5, 4, 9, 2, 6, 0, 7, 1};
+

          
+
    // 並べ替える前の並びを表示
+
    Print(data);
+

          
+
    System.out.println("ソート開始");
+

          
+
    // クイックソートによる並べ替え
+
    QSort(data, 0, data.length - 1);
+

          
+
    // 並べ替えた後の並びを表示
+
    System.out.println("ソート終了");
+

          
+
    Print(data);
+
  }
+

          
+
  // クイックソートの実装
+
  static void QSort(int[] data, int left, int right)
+
  {
+
    int j = left; // データの左端を仮の基準点とする
+
    int temp;
+

          
+
    for (int i = left + 1; i <= right; i++) {
+
      if (data[i] < data[left]) {
+
        // 基準点の値よりも小さい値を前方に移動する
+
        j++;
+

          
+
        temp = data[j];
 
        data[j] = data[i];
        data[j] = data[i];
 
        data[i] = temp;
        data[i] = temp;
 
      }
      }
 
    }
    }
 

        

        
+
    // 仮に置いた基準点の値を新しい基準点に置く
 
    temp = data[left];
    temp = data[left];
 
    data[left] = data[j];
    data[left] = data[j];
 
    data[j] = temp;
    data[j] = temp;
 

        

        
~
    Print(data);
    enumerate();
+

          
+
    // 新しい基準点の位置で範囲を2分割する
+

          
+
    // 基準点の左側に要素がある場合は、さらにその範囲内で並べ替えを行う
+
    if (left < j - 1)
+
      QSort(data, left, j - 1);
 

        

        
~
    // 基準点の右側に要素がある場合は、さらにその範囲内で並べ替えを行う
    qsort( left, j - 1 );
~
    if (j + 1 < right)
    qsort( j + 1, right );
+
      QSort(data, j + 1, right);
 
  }
  }
 

        

        
~
  static void Print(int[] data) {
  // 配列の要素を列挙する
~
    for (int i = 0; i < data.length; i++) {
  static void enumerate() {
~
      System.out.print(data[i] + ", ");
    for ( int i = 0; i < data.length; i++ ) {
-
      System.out.print( data[i] + ", " );
 
    }
    }
 
    System.out.println();
    System.out.println();
 
  }
  }
 
}
}
 
}}
}}
+
#tabpage-end
 

        

        
 
#prompt(実行結果){{
#prompt(実行結果){{
~
8, 3, 5, 4, 9, 2, 6, 0, 7, 1
37, 13, 28, 44, 97, 61, 42, 51, 73, 80, 
~
ソート開始
Start...
~
1, 3, 5, 4, 2, 6, 0, 7, 8, 9
28, 13, 37, 44, 97, 61, 42, 51, 73, 80, 
~
0, 1, 5, 4, 2, 6, 3, 7, 8, 9
13, 28, 37, 44, 97, 61, 42, 51, 73, 80, 
~
0, 1, 3, 4, 2, 5, 6, 7, 8, 9
13, 28, 37, 42, 44, 61, 97, 51, 73, 80, 
~
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
13, 28, 37, 42, 44, 51, 61, 97, 73, 80, 
~
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
13, 28, 37, 42, 44, 51, 61, 80, 73, 97, 
~
ソート終了
13, 28, 37, 42, 44, 51, 61, 73, 80, 97, 
~
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Finished...
-
13, 28, 37, 42, 44, 51, 61, 73, 80, 97,
 
}}
}}