CODEWITHSUNDEEP
javaalgorithmsortingquicksort
progresivoJS
progresivoJS

Reputation: 61

Quick sort : analysis of partitioning

I'm studying quick-sort in the course of Algorithms 4th, Robert Sedgewick.

I want to know the following partition of quicksort code's the number of compare in an array of length N.

private static int partition(Comparable[] a, int lo, int hi)
{
  int i = lo, j = hi+1;
  while (true)
  {
    while (less(a[++i], a[lo]))
      if (i == hi) break;

    while (less(a[lo], a[--j]))
      if (j == lo) break;

    if (i>= j) break;
    exch(a, i, j);
  }

  exch(a, lo, j);
  return j;
}

I want to know T(n) of code described above. ( compare )

In my thought, it takes ~2N compares.

The reason is because it takes N compares for i to move from left to right, and for j to move right to left respectively in an already sorted array such as an array (A,B,C,D,E,F,G,H).

compare = less()

Upvotes: 0

Views: 142

Answers (2)

progresivoJS
progresivoJS

Reputation: 61

My god, it's my mistake in the iteration of i.

In the course of finding i to stop, that takes only 1 compares.

So, It takes ~N Compares.

Upvotes: 0

qrius
qrius

Reputation: 631

The time complexity of this partition function is T(n) = O(n)

Upvotes: 0

Related Questions