sort.h

/** Sorting: Insertion & Bubble & Selection
    (Ascending ver.)
    [Update 08.13.15]: Quick Sort + Merge Sort
    - - -
    Note: use for compare numbers or chars (rewrite for compare strings)
**/

/*** Edit *///
typedef struct
{
  int key;
  // more element here
} elType;

/* Insert Sort */
void sortins (elType list[], int n)
{
  int i, j;
  elType next;

  for (i = 1; i < n; i++)
    {
      next = list[i];
		
      for (j = i - 1; j >= 0 && next.key < list[j].key; j--)
	{
	  list[j + 1] = list[j];
	}

      list[j+1] = next;
    }
}

/* Bubble Sort */
void sortbbl (elType list[], int n)
{
  int i, j;
  elType temp;

  for (i = 0; i < n - 1; i++)
    {
      for (j = i + 1; j < n; j++)
	{
	  if (list[j].key < list[i]. key)
	    {
	      temp = list[i];
	      list[i] = list[j];
	      list[j] = temp;
	    }
	}
    }
}

/* Selection Sort */
// more efficient than bubble sort
void sortslt (elType list[], int n)
{
  int i, j;
  int min;

  for (i = 0; i < n - 1; i++)
    {
      min = i;

      for (j = i + 1; j < n; j++)
	{
	  if (list[j].key < list[i].key)
	    {
	      min = j;
	    }
	}

      if (min != i)
	{
	  // swap
	  elType temp = list[i];
	  list[i] = list[min];
	  list[min] = temp;
	}
    }
}

/* Quick Sort */
void swap(elType *a, elType *b)
{
  elType temp;

  temp = *a;
  *a = *b;
  *b = temp;
}

void sortQuick(elType list[], int left, int right)
// right = length of list which contains elements - 1
// (not count block emty)
{
  int pivot;
  int i, j;

  if (left < right)
    {
      i = left;
      j = right + 1;
      // running from both sides

      pivot = list[left].key;

      do
	{
	  do
	    {
	      i++;
	    } while (list[i].key < pivot);

	  do
	    {
	      j--;
	    } while (list[j].key > pivot);

	  if (i < j)
	    {
	      swap(&list[i], &list[j]);
	    }
	} while (i < j);

      swap(&list[left], &list[j]);
      // now we have two partion

      sortQuick(list, left, j - 1);
      sortQuick(list, j + 1, right);
    }
}

/* Merge Sort */
/* Merge the two haves arr[l..m] and arr[m+1...r] */
void merge(elType arr[], int l, int m, int r)
{
	int nL = m - l + 1;
	int nR = r - m;
	// length of each partion

	elType L[nL], R[nR];
	// temp array for storing

	int i, iL, iR;
	// index of main arr and partion

	/* Copy data to temp arrays */
	for (iL = 0; iL < nL; iL++)
	{
		L[iL] = arr[l + iL];
	}
	for (iR = 0; iR < nR; iR++)
	{
		R[iR] = arr[m + 1 + iR];
	}

	/* Merge the temp arrays back to arr[l..m] */
	i = l; iL = 0; iR = 0;
	while (iL < nL && iR < nR)
	{
		if (L[iL].key < R[iR].key)
		{
			arr[i++] = L[iL++];
		}
		else
		{
			arr[i++] = R[iR++];
		}
	}

	/* Copy remaning of temp arrays */
	while (iL < nL)
	{
		arr[i++] = L[iL++];
	}
	while (iR < nR)
	{
		arr[i++] = R[iR++];
	}
}

void sortMerge(elType arr[], int l, int r)
// r = length of arr (contains element) - 1
{
	if (l < r)
	{
		int m = l + (r - l) / 2;
		// same (l + r)/2
		// avoid for large sum of l and r

		// recursivly solve
		sortMerge(arr, l, m);
		sortMerge(arr, m + 1, r);

		// merge two partion
		merge(arr, l, m, r);
	}
}