Sorting Arrays

Bubble Sort

Bubble sort compares adjacent pairs of elements and swaps them if they are in the wrong order. This process is repeated until the array is sorted.

Algorithm:

1. Compare each pair of adjacent elements
2. If they are in the wrong order, swap them
3. Repeat steps 1 and 2 for each element until the array is sorted

Example:

int n, v[100];
  // Read v[] with n elements
  bool sorted;
  int m = n;
  do
  {
      sorted = true;
      int p = m;
      for(int i = 0 ; i < p - 1 ; i ++)
      if(v[i] > v[i+1])
      {
           int temp = v[i];
           v[i] = v[i+1];
           v[i+1] = temp;
           sorted = false;
           m = i + 1;
      }
  }
  while(!sorted);

Selection Sort

Selection sort finds the smallest element in the array and swaps it with the first element. It then repeats this process for the rest of the array.

Algorithm:

1. Find the smallest element in the array and swap it with the first element
2. Find the smallest element in the remaining array and swap it with the second element
3. Repeat steps 1 and 2 for each element until the array is sorted

Example:

int n, X[100];
  // Read X[] with n elements
  for(int i = 0 ; i < n - 1 ; i ++)
      for(int j = i + 1 ; j < n ; j ++)
          if(X[i] > X[j])
          {
               int temp = X[i];
               X[i] = X[j];
               X[j] = temp;
          }

Insertion Sort

Insertion sort builds the sorted array one element at a time, inserting each element into its correct position.

Algorithm:

1. Start with the second element and compare it with the elements before it
2. Shift larger elements one position to the right to make space for the current element
3. Insert the current element into the correct position
4. Repeat steps 1-3 for each element until the array is sorted

Example:

for(int i = 1 ; i < n ; i ++)
  {
      int p = i;
      while(p > 0 && a[p] < a[p-1])
      {
          int temp = a[p];
          a[p] = a[p-1];
          a[p-1] = temp;
          p --;
      }
  }