Running Time of Quicksort

Sort by

recency

|

78 Discussions

|

  • + 0 comments
    import java.util.Scanner;
    
    public class CompareSorts {
    
        private static int quickSortSwaps = 0;
    
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            int[] arrQuickSort = new int[n];
            int[] arrInsertionSort = new int[n];
    
            for (int i = 0; i < n; i++) {
                int num = scanner.nextInt();
                arrQuickSort[i] = num;
                arrInsertionSort[i] = num;
            }
    
            int insertionSortShifts = insertionSort(arrInsertionSort);
            quickSort(arrQuickSort, 0, n - 1);
    
            int result = insertionSortShifts - quickSortSwaps;
            System.out.println(result);
    
            scanner.close();
        }
    
        public static void quickSort(int[] arr, int low, int high) {
            if (low < high) {
                int pivotIndex = partition(arr, low, high);
                quickSort(arr, low, pivotIndex - 1);
                quickSort(arr, pivotIndex + 1, high);
            }
        }
    
        public static int partition(int[] arr, int low, int high) {
            int pivot = arr[high];
            int i = low - 1;
    
            for (int j = low; j < high; j++) {
                if (arr[j] < pivot) {
                    i++;
                    swap(arr, i, j);
                }
            }
    
            swap(arr, i + 1, high);
            return i + 1;
        }
    
        public static void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            quickSortSwaps++; // Increment the swap count
        }
    
        public static int insertionSort(int[] arr) {
            int shifts = 0;
    
            for (int i = 1; i < arr.length; i++) {
                int key = arr[i];
                int j = i - 1;
    
                while (j >= 0 && arr[j] > key) {
                    arr[j + 1] = arr[j];
                    j--;
                    shifts++;
                }
    
                arr[j + 1] = key;
            }
    
            return shifts;
        }
    }
    
  • + 0 comments

    Full example in Ruby, using implementation from the previous challenges:

    def insertion_sort(arr)
        ops = 0
        i = 1
        while (i < arr.length)
            if arr[i] < arr[i - 1]
                value = arr[i]
                j = i-1
                while (j >= 0 && value < arr[j])
                    arr[j+1] = arr[j]
                    ops += 1
                    j -= 1
                end
                arr[j+1] = value
            end
            i += 1
        end
        ops
    end
    
    def partition_lomuto(arr, lo, hi)
        pivot = arr[hi]
        i = lo - 1
        lo.upto(hi) do |j|
           if arr[j] <= pivot
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
           end
        end
       [i, (i - lo + 1)]
    end
    
    def quicksort(arr, lo, hi)
        return 0 unless lo >= 0 && hi >= 0 && lo < hi
        pivot, ops_part= partition_lomuto(arr, lo, hi)
        quicksort(arr, lo, pivot - 1) + quicksort(arr, pivot + 1, hi) + ops_part
    end
    
    _n = gets.strip.to_i
    arr = gets.rstrip.split.map(&:to_i)
    puts insertion_sort(arr.clone) - quicksort(arr, 0, arr.length - 1)
    
  • + 0 comments
    # Enter your code here. Read input from STDIN. Print output to STDOUT
    import copy
    # Insertion sort Swaps
    def insertion_sort(arr):
        n = len(arr)
        counter_for_swaps = 0
        for i in range(1, n):
            val = arr[i]
            j = i-1
    
            while(j >= 0 and arr[j] > val):
                arr[j+1] = arr[j]
                counter_for_swaps += 1
                j -= 1
    
            arr[j+1] = val
        # print(*arr)
        return counter_for_swaps
    
    class Insertion:
        def __init__(self):
            self.count=0
        def insertionsort(self,a):
            for i in range(1,len(a)):
                key=a[i]
                j=i-1
                while j>=0 and a[j]>key:
                    self.count+=1
                    a[j+1]=a[j]
                    j-=1
                a[j+1]=key
            return self.count
    
    class QuickSort:
        def __init__(self):
            self.count=0
        def swap(self,b,c,d):
            temp=b[c]
            b[c]=b[d]
            b[d]=temp
            return b
        def partition(self,a,s,e):
            pivot=e
            pindex=s
            for i in range(s,e):
                if a[i]<=a[pivot]:
                    self.swap(a,i,pindex)
                    self.count+=1
                    pindex+=1
            self.count+=1
            self.swap(a,pindex,pivot)
            return pindex
        def quicksort(self,a,s,e):
            if s<e:
                pIndex=self.partition(a,s,e)
                self.quicksort(a, s, pIndex-1)
                self.quicksort(a, pIndex+1, e)
            return self.count
        
    if __name__ == '__main__':
        N = int(input())
        original = list(map(int,input().split()))
        duplicate = copy.deepcopy(original)
    
        insertion_counter_for_swaps = insertion_sort(original)
        # print(insertion_counter_for_swaps)
    
        # Quicky
        quicksort=QuickSort()
        start = 0
        end = N -1
        quicksort_counter_for_swaps = quicksort.quicksort(duplicate, start, end)
        print(insertion_counter_for_swaps - quicksort_counter_for_swaps)
    
  • + 0 comments
    # Enter your code here. Read input from STDIN. Print output to STDOUT
    
    def runningTimeIn(arr):
        count = 0
        for i in range(1,len(arr)):
            j = i-1
            key = arr[i]
            while (j>=0) and (arr[j]>key):
                arr[j+1]=arr[j]
                j -= 1
                count += 1
            arr[j+1]=key
        return count
    
    def partition(arr,low,high,swap):
        i = ( low-1 )         
        pivot = arr[high] 
        #swaps = 0
        for j in range(low , high): 
            if   arr[j] <= pivot: 
                i = i+1 
                arr[i],arr[j] = arr[j],arr[i]
                swap += 1
      
        arr[i+1],arr[high] = arr[high],arr[i+1] 
        swap += 1
        return i+1,swap 
      
    def runningTimeQ(arr,low,high,swap=0): 
        pi = 0
        if low < high:
            pi,swap = partition(arr,low,high,swap) 
            #print (' '.join(map(str, arr)))
            swap = runningTimeQ(arr, low, pi-1,swap) 
            swap = runningTimeQ(arr, pi+1, high,swap) 
        return swap
    
    if __name__ == '__main__':
        n = int(input())
    
        arr = list(map(int, input().rstrip().split()))
    
        arrCopy = []
        arrCopy.extend(arr)
        
        qRun = runningTimeQ(arr,0,n-1)
        
        inRun = runningTimeIn(arrCopy)
        
        result = inRun - qRun 
    
        print(result)
    
  • + 0 comments

    Pithon 3

    def runningTime(ar):
        counter = 0
        for j in range(len(ar)):
            for i in range(j, len(ar)):
                if ar[j] > ar[i]:
                    counter += 1
        return counter
    
    def Quicksort_In_Place(ar, start, end, counter=0):
        if end - start > 1:
            a = ar[end-1]
            s = start
            for i in range(start, end):
                if a >= ar[i]:
                    ar[s], ar[i] = ar[i], ar[s]
                    s += 1
                    counter += 1
            counter = Quicksort_In_Place(ar, start, s-1, counter)
            counter = Quicksort_In_Place(ar, s, end, counter)
        return counter
    
    n = int(input())
    ar = list(map(int, input().split()))
    print(runningTime(ar) - Quicksort_In_Place(ar, 0, n))