I want to write an algorithm to remove duplicates and sort an array with single loop in javascript. I want to do it with algorithms not declarative methods. I can sort it with single loop but can't remove duplicates. I will be glad if someone help me.

Number of elements in array is 10^6, each element is equal to or greater than 0, less than 300

This is my sorting algorithm:

var a = [2, 7, 5, 1, 3, 2, 7];

for (let i = 0; i < a.length - 1; i  ) {
  if (a[i] > a[i   1]) {
    let temp = a[i]
    a[i] = a[i   1]
    a[i   1] = temp
    i = -1
  }
}

console.log(a)

CodePudding user response：

It's honorable that you was curious enough to try to find a solution, even after the interview. A good sign for a programmer.

1. I would use an object to keep track of any duplicates.
2. Also loop from the end, mostly because it feels right, not messing up the index.
3. Change position in a if current < previous
4. Else add to the object.
5. Check if object has previous index, or
6. Check if current is the same as previous (ex. 7, 7 at the end of the array)
7. then splice the previous index.
8. Added numberOfLoops just because it's fun to know.

var a = [2, 2, -1, 8, 5, 1, 3, 3, 13, 2, 8, 8];
var temp = {};  // 1
var result = [];
var current, previous;
var numberOfLoops = 0;

for (let i = a.length - 1; i > 0 ; i--) {  // 2
  current = a[i];
  previous = a[i - 1];
  numberOfLoops  ;  // 8

  if (temp.hasOwnProperty(previous) ||   // 5
      current == previous) {             // 6
    a.splice(i - 1, 1);                  // 7
    // i  ;
  } else if (current < previous) {  // 3
    a[i - 1] = current;
    a[i] = previous;
    i  = 2;
    delete temp[current];
  } else {                          // 4
    temp[current] = current;
  }
}

console.log({numberOfLoops});  // 8
console.log(a);  // [-1, 1, 2, 3, 5, 8, 13]