CODEWITHSUNDEEP
javascript
ammar ammary
ammar ammary

Reputation: 119

sort random array using only one loop without sort function

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]));
});

Upvotes: 1

Views: 1169

Answers (4)

Christoph Eikermann
Christoph Eikermann

Reputation: 1

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

Upvotes: 0

Matus Dubrava
Matus Dubrava

Reputation: 14512

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);

Upvotes: 0

Jonathan Rys
Jonathan Rys

Reputation: 1886

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

enter image description here

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.

Upvotes: 0

Jonas Wilms
Jonas Wilms

Reputation: 138557

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.

Upvotes: 1

Related Questions