java - Cyclic Sort Implemenation - Stack Overflow

admin管理员组

文章数量:1401199

I was just trying to implement cyclic sort after watching the theory part of a YouTube video (;t=889).

I came up with the below code,

    public static void cyclicSort(int[] arr) {
        for(int i = 0; i < arr.length - 1; i++) {
            while(arr[i] != i+1) {
                swap(arr, i, arr[i]-1);
            }
        }
    }

But the video implements the sort algo as below,

    public static void cyclicSort2(int[] arr) {
        int i = 0;
        while(i < arr.length) {
            int correctIndex = arr[i] - 1;
            if(arr[i] != arr[correctIndex]) {
                swap(arr, i, correctIndex);
            } else {
                i++;
            }
        }
    }

I wanted to understand, will there be any changes to the time complexity in my implementation because of the nested loop ? Also I can see that my code is a little less readable.

Thanks in advance.

I was just trying to implement cyclic sort after watching the theory part of a YouTube video (https://youtu.be/JfinxytTYFQ?list=PL9gnSGHSqcnr_DxHsP7AW9ftq0AtAyYqJ&t=889).

I came up with the below code,

    public static void cyclicSort(int[] arr) {
        for(int i = 0; i < arr.length - 1; i++) {
            while(arr[i] != i+1) {
                swap(arr, i, arr[i]-1);
            }
        }
    }

But the video implements the sort algo as below,

    public static void cyclicSort2(int[] arr) {
        int i = 0;
        while(i < arr.length) {
            int correctIndex = arr[i] - 1;
            if(arr[i] != arr[correctIndex]) {
                swap(arr, i, correctIndex);
            } else {
                i++;
            }
        }
    }

I wanted to understand, will there be any changes to the time complexity in my implementation because of the nested loop ? Also I can see that my code is a little less readable.

Thanks in advance.

• java
• algorithm
• sorting
• array-algorithms

Share Improve this question Follow edited Mar 24 at 20:13 PaulMcKenzie 35.5k44 gold badges2626 silver badges4848 bronze badges asked Mar 24 at 15:42 Nishanth K NNishanth K N 2333 bronze badges 2

• Do not tag this as dsa. The dsa tag is for Digital Signature Algorithm. Please read the tag definition before applying them to your question. – PaulMcKenzie Commented Mar 24 at 20:13
• Video solution seems not to be sorting: int correctIndex = arr[i] - 1; note, that if arr = [-10, -20, -30] then ` arr[correctIndex]` will throw exception. Note that video is not about sorting but solving LeetCode problem. – Dmitrii Bychenko Commented Mar 26 at 16:49

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 2

will there be any changes to the time complexity in my implementation because of the nested loop ?

No because the video version is also has the equivalent of a nested loop when it does a swap and doesn't increment i. I don't know why the video version outer loop is to i < arr.length, since if the last element is out of order, then at least one earlier element is out of order, but all of the earlier elements are in place by the time of the last outer loop.

The following code is a C example that uses a local variable to hold a temporary value while going through each cycle by only storing one value at a time which should be a bit faster than swapping which stores two values at a time. The other local variables are there mostly for readability, and to more closely match the code that an optimizing compiler would generate.

void cycle_sort(int *a, int n)          /* cycle_sort values 1->n */
{
int e;                                  /* current element of a[] */
int f;                                  /* next    element of a[] */
int p;                                  /* cycle_sorted position for e */
int s;                                  /* start of cycle */
    n--;                                /* no need to check last element */
    for(s = 0; s < n; s++){             /* scan for cycles */
        e = a[s];                       /* get e */
        p = e-1;                        /* set p */
        if(p == s)                      /* if in place continue */
            continue;
        do{                             /* process a cycle */
            f = a[p];                   /*  get f (save a[p]) */
            a[p] = e;                   /*  put e into place */
            e = f;                      /*  update e */
            p = e-1;                    /*  update p */
        }while (p != s);                /*  repeat until end of cycle */
        a[s] = e;                       /*  put e into place */
    }
}

本文标签： javaCyclic Sort ImplemenationStack Overflow