Sorting

Exchange Sort

Pinterest LinkedIn Tumblr

The exchange sort is a sorting algorithm that compares each item with other items of the array and swap the item if requires.

Sort the items by exchanging pairs of items until the sequence is sorted. In general, an algorithm may exchange adjacent elements as well as widely separated one.

source Code

package com.dsacode.Algorithm.sorting;
 
import java.util.Arrays;
 
public class ExchangeSort {
 
    public static void sort( int[] array)  {
         int temp;
          for (int i=0; i < array.length-1; i++) {
             for (int j = i+1; j < array.length; j++) {
                if(array[ i ] > array[ j ]) {
                   temp = array[i];
                   array[i] = array[j];
                   array[j] = temp;
                }          
             }
          }
    }
    public static void main(String[] args) {
         int arr[] = {12, 11, 13, 5, 6, 7};
          System.out.println("unsorted array before sorting : " + Arrays.toString(arr));
         sort(arr);
          System.out.println("Sorted array After ExchangeSort sorting : " + Arrays.toString(arr));
 
    }
 
}

Output

Unsorted array before sorting: [12, 11, 13, 5, 6, 7]
Sorted array After Exchange Sort sorting: [5, 6, 7, 11, 12, 13]

Algorithm Explanation

Exchange of an adjacent pair of elements.
Overall sort consists of a number of passes over the data.
Each pass starts at one end of the array and works toward the other end.
Each pair of elements that are out of order are exchanged.

Time Complexity

Best CaseAverage CaseWorst Case
O(n^2)O(n^2)O(n^2)

Reference

  1. http://www.ee.ryerson.ca/~courses/coe428/sorting/exchangesort.html
  2. http://www.macs.hw.ac.uk/~pjbk/pathways/cpp2/node68.html

Write A Comment