sort random array using only one loop without sort function

Question

can i sort random array using only one loop without using sort function ??? but can i do the same using one for loop ? how can i do that ? here i'm use nested loop

$(document).ready(function () {
  function sortarr(arr) {
    for (var i = 0; i < arr.length; i++) {
      for (var j = i + 1; j < arr.length; j++) {
        if (arr[i] > arr[j]) {
          var temp = arr[i];
          arr[i] = arr[j];
          arr[j] = temp;
        }
      }
    }
    return arr;
  }
  console.log(sortarr([10, 18, 4, 5, 9, 6, 16, 12]));
});

console.log(sortarr([10,18,4,5,9,6,16,12]));}); what's going on with this line here? — Sterling Archer
– Sterling Archer, Commented May 11, 2018 at 20:06
I mean, I guess technically, you can keep resetting your array counter back to the beginning until the array is sorted, rather than using nested loops.. but the big O time complexity would be the same. What is your use-case? — mhodges
– mhodges, Commented May 11, 2018 at 20:08
That depends on what you mean by one loop. Any comparison sort's time complexity is bounded from below by n * lg n therefore you can't sort it by just one loop, that would be sorting in n time complexity. — Matus Dubrava
– Matus Dubrava, Commented May 11, 2018 at 20:09
@ammarammary Just about every built-in sort function to any language uses a quick sort or merge sort (or something similar), which is O(n*log(n)). The exact implementation in JavaScript is browser-dependent, as it is not defined in the spec. — mhodges
– mhodges, Commented May 11, 2018 at 20:16

Jonas Wilms · Accepted Answer · 2018-05-11 20:23:40Z

1

You could do mergesort with one loop only:

function mergeSort(arr) {
  if(arr.length < 2) return arr

  const a = mergeSort(arr.slice(0, arr.length / 2)),
             b = mergeSort(arr.slice(arr.length / 2));

 const result = [];

  while(a.length && b.length)
    result.push((a[0] > b[0] ? a : b).shift());

  return result.concat(a, b);
}

But as outlined in the comments above, this won't be faster than an approach with multiple loops, probably slower.

answered May 11, 2018 at 20:23

Jonas Wilms

139k20 gold badges164 silver badges164 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Matus Dubrava · Accepted Answer · 2018-05-11 21:20:37Z

If you are interested, this is how you might implement your own quicksort.

But note that using default js sort would be much faster than any implementation that you can do yourself (most probably) as that sort is optimized to run as fast as possible. This is just an implementation of a generic textbook quicksort.

const quicksort = arr => {

  const _partition = (arr, begin, end) => {
    let pivot = begin;
    for (let i = begin; i <= end; i++) {
      if (arr[i] < arr[begin]) {
        pivot++;
        [arr[pivot], arr[i]] = [arr[i], arr[pivot]];
      }
    }
    [arr[begin], arr[pivot]] = [arr[pivot], arr[begin]];
    return pivot;
  }

  const _quicksort = (arr, begin, end) => {
    if (begin < end) {
      const pivot = _partition(arr, begin, end);
      _quicksort(arr, begin, pivot - 1);
      _quicksort(arr, pivot + 1, end);
    }
  }

  _quicksort(arr, 0, arr.length);
}

const arr = [10, 18, 4, 5, 9, 6, 16, 12];
quicksort(arr);
console.log(arr);

And you can make it a little bit faster (in some cases) by randomizing the pivot selection like this.

const quicksort = arr => {

  const _partition = (arr, begin, end) => {
    let pivot = begin;
    for (let i = begin; i <= end; i++) {
      if (arr[i] < arr[begin]) {
        pivot++;
        [arr[pivot], arr[i]] = [arr[i], arr[pivot]];
      }
    }
    [arr[begin], arr[pivot]] = [arr[pivot], arr[begin]];
    return pivot;
  }

  const _randomizedPartition = (arr, begin, end) => {
    const index = Math.floor(Math.random() * (end-begin)) + begin;
    [arr[begin], arr[index]] = [arr[index], arr[begin]];
    return _partition(arr, begin, end);
  }

  const _quicksort = (arr, begin, end) => {
    if (begin < end) {
      const pivot = _randomizedPartition(arr, begin, end);
      _quicksort(arr, begin, pivot - 1);
      _quicksort(arr, pivot + 1, end);
    }
  }

  _quicksort(arr, 0, arr.length);
}

const arr = [10, 18, 4, 5, 9, 6, 16, 12];
quicksort(arr);
console.log(arr);

Jonathan Rys · Accepted Answer · 2018-05-11 20:27:51Z

0

Here's a chart showing various sorting algorithms and their complexities:

A single pass through a loop without recursion or nesting is O(n), so no, not in the worst case. There are other techniques for sorting that can be incorporated to sort an array using a single loop as Jonas W. shows, but their time complexity isn't necessarily as good as good old .sort() which is Quicksort.

answered May 11, 2018 at 20:27

Jonathan Rys

1,8661 gold badge15 silver badges28 bronze badges

Comments

Christoph Eikermann · Accepted Answer · 2022-07-20 11:58:25Z

0

you can sort a random array using only one loop without using sort function

a = [10, 18, 4, 5, 9, 6, 16, 12];
for(i=0; i< a.length-1;(a[i]>a[i+1]) ? ((a[i]=a[i]^a[i+1]) && (a[i+1]=a[i]^a[i+1]) && (a[i]=a[i]^a[i+1]) && (i=0)): i++) {}
console.log(a); // 4, 5, 6, 9, 10, 12, 16, 18

answered Jul 20, 2022 at 11:58

Christoph Eikermann

1

1 Comment

ahuemmer Over a year ago

Welcome to SO! Please don't post code-only answers but add a little textual explanation about how and why your approach works and what makes it different from the other answers given. You may also have a look at our "How to write a good answer" entry.

Collectives™ on Stack Overflow

sort random array using only one loop without sort function

4 Answers 4

Comments

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related