Faits:
A.
A.a. O._ est au bénéfice d'une formation universitaire en mathématiques et d'un Master in Business Information Systems (MBI). Après avoir occupé différents postes d'enseignant et de chercheur en mathématiques à l'étranger à X._ et à Y._, il a exercé la fonction de ministre conseiller de l'ambassade de X._ à T._ et de représentant permanent de X._ auprès du Conseil de l'Europe de 1993 à 1997. Il a ensuite travaillé comme responsable des services informatiques auprès de Z._ de 1998 à 2006, de W._ de 2006 à 2009 et de V._ de février à juin 2009. Il est inscrit à l'assurance-chômage depuis le 1 er juin 2009.
Le 23 juin 2010, O._ a demandé à son conseiller en placement l'autorisation de suivre une formation pédagogique sans perdre ses indemnités de chômage. Par décision du 12 juillet 2010, le Service de l'emploi du canton de Vaud a refusé cette demande au motif qu'il s'agissait d'une formation de base qui ne pouvait pas être prise en charge par l'assurance-chômage. L'assuré s'est opposé à cette décision par lettre du 2 août 2010. Il exposait notamment que le contrat de durée déterminée qui lui avait été proposé dans le domaine de l'enseignement par une école privée représentait pour le moment l'unique ouverture vers le monde du travail et qu'il lui paraissait logique de concentrer désormais ses efforts dans la direction de l'enseignement. Il soutenait que si tout le monde était d'accord pour reconnaître la qualité de ses diplômes académiques, il lui manquait la formation pédagogique exigée par toute les écoles publiques et par certaines écoles privées, raison pour laquelle il souhaitait suivre une telle formation à l'Université de U._. Il a en outre précisé que, dans tous les cas, il poursuivrait ses recherches d'emploi et privilégierait une proposition d'emploi intéressante par rapport à sa formation.
Ayant appris que l'assuré allait débuter une formation auprès de l'Université de U._, le Service de l'emploi l'a informé, le 10 août 2010, qu'il examinerait son aptitude au placement et lui a adressé à cet effet un questionnaire. O._ a répondu le 19 août 2010 qu'il souhaitait suivre une formation pédagogique uniquement dans le but d'obtenir le droit d'accès à l'enseignement public post-obligatoire mais qu'il renoncerait immédiatement à cette formation pour la reprise d'une activité professionnelle ou pour suivre une mesure octroyée par l'ORP lui apportant les mêmes qualifications que dite formation. Il a en outre précisé que la formation était normalement prévue sur une année mais qu'à sa demande, l'Université de U._ avait accepté un cursus de deux ans débutant le 20 septembre 2010 et que les frais de scolarité s'élevaient à 543 fr. par année.
Par une nouvelle décision du 20 août 2010, le Service de l'emploi a rejeté l'opposition.
A.b. Sur demande du Service de l'emploi, O._ a indiqué le 10 septembre 2010 avoir pris la décision d'entreprendre la formation envisagée, précisant qu'il poursuivrait ses recherches d'emploi et qu'en cas de proposition d'emploi ou d'une mesure proposée par l'ORP, il abandonnerait immédiatement sa formation. Dans un courrier du 17 septembre 2010, il a informé le Service de l'emploi qu'il renonçait à recourir contre la décision sur opposition du 20 août 2010. Il a rappelé que la formation prévue augmentait son aptitude au placement, dans la mesure où elle assurait un enseignement dans différentes écoles, notamment publiques. En outre, elle était exercée dans une si faible mesure qu'elle n'avait pas d'incidence sur son aptitude au placement, ce d'autant moins qu'il était prêt à y renoncer s'il trouvait un emploi adéquat ou si l'assurance-chômage lui offrait de suivre toute mesure à cet effet.
Le 6 octobre 2010, l'assuré a répondu à un nouveau questionnaire du Service de l'emploi: aucun stage n'était prévu pendant sa formation, il n'était pas rémunéré pendant celle-ci et il était totalement disposé à renoncer au suivi de sa formation et à sa pratique pédagogique pour prendre une activité salariée dans son domaine de base ou pour suivre une mesure du marché du travail octroyée par l'ORP. Il a par ailleurs produit une attestation du 12 octobre 2010 de l'Université de U._, dont il ressort que le plan d'études sur deux ans est basé sur le principe d'une activité professionnelle à 50 % parallèlement au suivi des cours (lundi après-midi et vendredi matin) et du stage (4 heures par semaine).
Par décision du 11 novembre 2010, le Service de l'emploi a prononcé l'aptitude au placement de O._ avec une perte de travail à prendre en considération de 50 % à compter du 20 septembre 2010. L'assuré a formé opposition. Le Service de l'emploi lui a ensuite demandé de produire copie des listes de "preuves de recherches personnelles effectuées en vue de trouver un emploi" des mois de septembre 2010 à janvier 2011 ainsi que tout document attestant du programme des stages et de la modification de l'horaire des cours depuis le 17 décembre 2010. O._ a répondu qu'il était dans l'impossibilité de transmettre une autre liste des preuves de recherches d'emploi effectuées de septembre 2010 à janvier 2011 que celle déjà en possession du Service de l'emploi. Il tenait cependant à disposition sur un CD-Rom les offres qu'il avait faites. Il a par ailleurs rappelé les horaires des cours théoriques. S'agissant de la pratique pédagogique, il a indiqué qu'il devait effectuer, pour chaque matière, 4 périodes hebdomadaires de 45 minutes pendant 42 semaines au cours de l'année 2010-2011. Les horaires de la pratique pédagogique ne pouvaient pas être aussi réguliers que ceux des cours théoriques dans la mesure où il fallait s'adapter aux horaires des classes suivies, en fonction des thèmes enseignés.
Le 18 mars 2011, le Service de l'emploi a informé l'assuré qu'il envisageait de modifier la décision litigieuse à son détriment. Il l'a ainsi invité à dire s'il entendait maintenir ou retirer son opposition. O._ ayant maintenu son opposition, le Service de l'emploi l'a rejetée par une nouvelle décision du 16 mai 2011. Il a en outre réformé sa décision du 11 novembre 2010 en ce sens que l'assuré était inapte au placement depuis le 20 septembre 2010.
B.
O._ a déféré la décision sur opposition du 16 mai 2011 à la Cour des assurances sociales du Tribunal cantonal vaudois. Il a conclu à sa réforme, en ce sens qu'il était reconnu apte au placement dès le 20 septembre 2010.
Une audience d'instruction s'est tenue le 17 février 2012 au cours de laquelle deux témoins ont été entendus, dont le conseiller en placement de l'assuré.
Statuant le 22 juin 2012, la juridiction cantonale a admis le recours et réformé la décision en ce sens que les indemnités de chômage continueraient à être versées à O._ dès le 20 septembre 2010.
C.
Le Service de l'emploi interjette un recours en matière de droit public contre ce jugement dont il demande l'annulation, en concluant à la confirmation de sa décision du 16 mai 2011.
O._ conclut au rejet du recours.
La juridiction cantonale et le Secrétariat d'Etat à l'économie (SECO) ont renoncé à se déterminer sur le recours.

Considérant en droit:
1.
Le recours est dirigé contre un arrêt final (<ref-law>) rendu en matière de droit public (<ref-law>) par une autorité cantonale de dernière instance (art. 86 al. 1 let. d LTF). Il a été déposé dans le délai (<ref-law>) et la forme (<ref-law>) prévus par la loi. Il est donc recevable.
2.
Le Tribunal fédéral, qui est un juge du droit, fonde son raisonnement juridique sur les faits retenus par l'autorité précédente (<ref-law>), sauf s'ils ont été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire - ou en violation du droit au sens de l'<ref-law> (cf. <ref-law>). Si le recourant entend s'écarter des constatations de fait de l'autorité précédente, il doit expliquer de manière circonstanciée en quoi les conditions de l'<ref-law> seraient réalisées. A défaut, un état de fait divergent de celui de la décision attaquée ne peut être pris en compte (<ref-ruling> consid. 1.5 p. 68).
3.
Le litige porte sur l'aptitude au placement de l'intimé depuis le 20 septembre 2010.
4.
Selon la jurisprudence, lorsqu'un assuré fréquente un cours durant la période de chômage (sans que les conditions des <ref-law> soient réalisées), il doit, pour être reconnu apte au placement, être disposé - et être en mesure de le faire - à arrêter le cours pour reprendre un emploi, tout en remplissant pleinement son obligation de recherches d'emploi. Les exigences en matière de disponibilité et de flexibilité sont plus élevées lorsqu'il s'agit d'un assuré suivant un cours de par sa propre volonté et à ses frais. Il est alors tenu de poursuivre ses recherches d'emploi de manière qualitativement et quantitativement satisfaisantes et être disposé à interrompre le cours en tout temps. Cette dernière condition doit toutefois découler de données objectives; de simples allégations de l'assuré ne suffisent pas (cf. <ref-ruling> consid. 4 p. 266 s.; DTA 2004 n. 2 p. 46 [C 136/02] consid. 1.3; arrêt 8C_466/2010 du 8 février 2011, consid. 3).
5.
Le Service de l'emploi fait valoir qu'en assimilant l'inaptitude au placement de l'assuré à une sanction, la juridiction cantonale a procédé à une interprétation erronée de l'<ref-law>.
Il est vrai qu'en l'espèce, l'inaptitude au placement prononcée par le recourant ne consistait pas en une sanction. Les premiers juges se sont néanmoins référés aux règles et principes jurisprudentiels applicables en matière d'aptitude au placement. Quant à l'expression "sanction d'inaptitude" qu'ils ont utilisée, il s'agit d'un élément mineur de leur motivation qui n'a aucune incidence sur le contenu matériel du jugement attaqué et ne saurait, en soi, conduire à l'annulation de ce dernier.
6.
En l'espèce, la juridiction cantonale a retenu que l'assuré avait invariablement déclaré à plusieurs reprises qu'en cas de proposition d'emploi, il privilégierait celle-ci à sa formation. Ces déclarations étaient confirmées par son conseiller ORP, selon lequel l'assuré n'aurait pas poursuivi sa formation s'il avait trouvé un emploi équivalent, soit un emploi correspondant à ses compétences et à peu près de même niveau. Le conseiller ORP n'avait toutefois jamais eu d'emploi convenable ni une mesure temporaire à lui proposer. L'intimé avait par ailleurs toujours respecté ses obligations légales en matière de recherches d'emploi, aucune baisse de régime n'ayant pu être constatée pendant sa formation. Enfin, le coût de la formation, à savoir 543 fr. par année, ne constituait pas un investissement financier tel qu'il apparaissait difficilement concevable que l'intimé l'interrompe pour prendre un autre emploi.
7.
7.1. Le recourant se prévaut d'une appréciation arbitraire des faits. En substance, il reproche à la juridiction cantonale d'avoir fait fi de divers éléments de faits tendant à démontrer que l'assuré ne présentait pas une disponibilité suffisante quant au temps qu'il pouvait consacrer à un emploi et quant au nombre d'employeurs potentiels. Les premiers juges n'auraient ainsi pas tenu compte du fait que l'assuré avait constamment fait part de sa motivation à suivre la formation pédagogique entreprise, celle-ci étant la condition sine qua non pour accéder à l'enseignement public post-obligatoire. En plus de sa formation théorique, l'assuré devait effectuer une formation pratique, soit 4 périodes hebdomadaires de 45 minutes pendant 42 semaines sur l'année scolaire 2010-2011. En outre, l'assuré recherchait uniquement des emplois à plein temps dans le domaine de l'informatique, où les possibilités de travailler en soirée ou le week-end étaient pratiquement inexistantes.
7.2. Déterminer si un assuré est disposé à suivre un cours (supra consid. 4) est une question de fait. Le recourant ne parvient pas à démontrer le caractère arbitraire des constatations de fait de la juridiction cantonale. Sur ce point, son argumentation tend plutôt à substituer sa propre appréciation à celle de l'autorité précédente. En ce qui concerne les faits susceptibles, selon lui, de nier l'aptitude au placement de l'assuré, on ne voit pas en quoi l'horaire des cours théoriques et pratiques de l'assuré l'aurait empêché de mettre en tout temps un terme à sa formation s'il trouvait un emploi. Quant au fait que l'assuré ne recherchait que des emplois à plein temps, il constitue plutôt un indice supplémentaire que l'intimé privilégiait une proposition d'emploi par rapport à sa formation. Au demeurant, l'intimé n'a pas limité ses recherches d'emploi dans le domaine informatique (cf. jugement attaqué, p. 21). Enfin, on précisera que l'autorité cantonale ne s'est pas uniquement fondée sur les déclarations de l'intimé mais qu'elle a également tenu compte d'autres éléments objectifs (recherches d'emploi de l'assuré pendant sa formation, coût de la formation, déclarations de témoins) pour en déduire, au degré de la vraisemblance prépondérante, que l'intimé a toujours donné la priorité à la reprise d'une activité lucrative plutôt qu'à sa formation. Les affirmations du recourant, de nature appellatoire, ne permettent pas de s'écarter des faits retenus par la juridiction cantonale. En tant qu'il conteste l'aptitude au placement de l'intimé à partir du 20 septembre 2010, le recours se révèle dès lors mal fondé.
8.
Le recourant fait encore valoir que la décision sur opposition du 16 mai 2011 ne portait que sur l'aptitude au placement de l'assuré, de sorte qu'en imposant le versement de prestations à l'assuré, le jugement entrepris sort de l'objet de la contestation et doit être annulé.
La décision sur opposition rendue le 16 mai 2011 par le Service de l'emploi portait exclusivement sur l'aptitude au placement de l'assuré, comme le souligne à juste titre le recourant. Par conséquent, en tant qu'il impose le versement des prestations à l'intimé et ne se limite pas à constater son aptitude ou son inaptitude au placement, le jugement entrepris sort de l'objet de la contestation (cf. arrêt 8C_627/2009 du 8 juin 2010, consid. 1). Par conséquent, le jugement entrepris doit être réformé sur ce point, en ce sens que l'aptitude au placement de l'intimé est reconnue dès le 20 septembre 2010. Le recours doit, partant, être partiellement admis.
9.
Vu l'issue du litige, l'intimé peut prétendre une indemnité de dépens à la charge du recourant (<ref-law>). Par ailleurs, il n'y a pas lieu de prélever des frais judiciaires bien que le Service de l'emploi succombe sur l'objet du litige (<ref-law>; <ref-ruling> consid. 4.5 p. 642). Il n'y a pas lieu, par ailleurs, de modifier la décision de l'autorité précédente sur les dépens (cf. <ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est partiellement admis. Le chiffre II de la décision de la Cour des assurances sociales du Tribunal cantonal vaudois, du 22 juin 2012, est réformé en ce sens que l'aptitude au placement de l'intimé est reconnue. Le recours est rejeté pour le surplus.
2.
Il n'est pas perçu de frais judiciaires.
3.
Le recourant versera à l'intimé la somme de 2'000 fr. à titre de dépens pour la procédure devant le Tribunal fédéral.
4.
Le présent arrêt est communiqué aux parties, au Tribunal cantonal du canton de Vaud, Cour des assurances sociales, et au Secrétariat d'Etat à l'économie (SECO).
Lucerne, le 29 août 2013
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Juge présidant: Ursprung
La Greffière: Fretz Perrin